Limiting shape of the Depth First Search tree in an Erd\H{o}s-R\'enyi graph
| Autor: | Nathanaël Enriquez, Laurent Ménard, Gabriel Faraud |
|---|---|
| Přispěvatelé: | Modélisation aléatoire de Paris X (MODAL'X), Université Paris Nanterre (UPN), ANR-14-CE25-0014,GRAAL,GRaphes et Arbres ALéatoires(2014), ANR-10-LABX-0023,UnivEarthS,Earth - Planets - Universe: observation, modeling, transfer(2010), Ménard, Laurent, Appel à projets générique - GRaphes et Arbres ALéatoires - - GRAAL2014 - ANR-14-CE25-0014 - Appel à projets générique - VALID, Earth - Planets - Universe: observation, modeling, transfer - - UnivEarthS2010 - ANR-10-LABX-0023 - LABX - VALID, Marches aléatoires en interaction - - MALIN2016 - ANR-16-CE93-0003 - AAPG2016 - VALID, ANR-16-CE93-0003,MALIN,Marches aléatoires en interaction(2016) |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
[MATH.MATH-PR] Mathematics [math]/Probability [math.PR]
Theoretical computer science Computer science Applied Mathematics General Mathematics Nuclear Theory 0102 computer and information sciences Limiting 01 natural sciences Computer Graphics and Computer-Aided Design [MATH.MATH-PR]Mathematics [math]/Probability [math.PR] 010104 statistics & probability Search engine 010201 computation theory & mathematics Condensed Matter::Superconductivity 60K35 82C21 60J20 60F10 Condensed Matter::Statistical Mechanics Graph (abstract data type) Depth-first search 0101 mathematics Software Mathematics - Probability |
| Zdroj: | Random Structures and Algorithms Random Structures and Algorithms, Wiley, 2020, 56 (2) Random Structures and Algorithms, 2020, 56 (2) |
| ISSN: | 1042-9832 1098-2418 |
| Popis: | We show that the profile of the tree constructed by the Depth First Search Algorithm in the giant component of an Erd\H{o}s-R\'enyi graph with $N$ vertices and connection probability $c/N$ converges to an explicit deterministic shape. This makes it possible to exhibit a long non-intersecting path of length $\left( \rho_c - \frac{\mathrm{Li}_2(\rho_c)}{c} \right) \times N$, where $\rho_c$ is the density of the giant component. Comment: 16 pages, 3 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text