EUVIMEDEUVIMED entdecken
Crossref

Giant Components in Random Temporal Graphs

Ruben Becker, Arnaud Casteigts, Pierluigi Crescenzi, Bojana Kodric, Michael Raskin, Malte Renken, Viktor Zamaraev

SIAM Journal on Discrete Mathematics · 30.06.2026 · 40 (2) · 449-485

DOI: 10.1137/24m1673206 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 01.04.2026. Verfasst von Ruben Becker und 6 weiteren Autor:innen. Die Arbeit nennt 41 Literaturangaben. Gefördert von: Agence Nationale de la Recherche, Deutsche Forschungsgemeinschaft, European Research Council.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A temporal graph is a graph whose edges appear only at certain points in time. Recently, the second and the last three authors proposed a natural temporal analog of the Erdős–Rényi random graph model. The proposed model is obtained by randomly permuting the edges of an Erdős–Rényi random graph and interpreting this permutation as an ordering of presence times. It was shown that the connectivity threshold in the Erdős–Rényi model fans out into multiple phase transitions for several distinct notions of reachability in the temporal setting. In the present paper, we identify a sharp threshold for the emergence of a giant temporally connected component. We show that at [Formula: see text] the size of the largest temporally connected component increases from [Formula: see text] to [Formula: see text]. This threshold holds for both open and closed connected components, i.e., components that allow (respectively, forbid) their connecting paths to use external nodes.

Förderung

  • Agence Nationale de la Recherche
  • Deutsche Forschungsgemeinschaft
  • European Research Council

Zitieren

APA

Becker, R., Casteigts, A., Crescenzi, P., Kodric, B., Raskin, M., Renken, M., & Zamaraev, V. (2026). Giant Components in Random Temporal Graphs. SIAM Journal on Discrete Mathematics, 40(2), 449-485. https://doi.org/10.1137/24m1673206

Vancouver

Becker R, Casteigts A, Crescenzi P, Kodric B, Raskin M, Renken M, et al. Giant Components in Random Temporal Graphs. SIAM Journal on Discrete Mathematics. 2026;40(2):449-485. doi:10.1137/24m1673206

BibTeX
@article{Becker2026,
  author = {Becker, Ruben and Casteigts, Arnaud and Crescenzi, Pierluigi and Kodric, Bojana and Raskin, Michael and Renken, Malte and Zamaraev, Viktor},
  title = {Giant Components in Random Temporal Graphs},
  journal = {SIAM Journal on Discrete Mathematics},
  year = {2026},
  volume = {40},
  number = {2},
  pages = {449--485},
  doi = {10.1137/24m1673206}
}
Kostenlos starten →