Geodesic
On the performance of the depth first search algorithm in supercritical random graphs
Sahar Diskin1 ; Michael Krivelevich1
1Tel Aviv University
The electronic journal of combinatorics, Tome 29 (2022) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We consider the performance of the Depth First Search (DFS) algorithm on the random graph $G\left(n,\frac{1+\epsilon}{n}\right)$, $\epsilon>0$ a small constant. Recently, Enriquez, Faraud and Ménard proved that the stack $U$ of the DFS follows a specific scaling limit, reaching the maximal height of $\left(1+o_{\epsilon}(1)\right)\epsilon^2n$. Here we provide a simple analysis for the typical length of a maximum path discovered by the DFS.
DOI : 10.37236/10894
Classification : 05C85, 05C80
Mots-clés : spanning tree, analysis of the performance

Sahar Diskin  1   ; Michael Krivelevich  1

1 Tel Aviv University 
@article{10_37236_10894,
     author = {Sahar Diskin and Michael Krivelevich},
     title = {On the performance of the depth first search algorithm in supercritical random graphs},
     journal = {The electronic journal of combinatorics},
     year = {2022},
     volume = {29},
     number = {3},
     doi = {10.37236/10894},
     zbl = {1498.05261},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/10894/}
}
TY  - JOUR
AU  - Sahar Diskin
AU  - Michael Krivelevich
TI  - On the performance of the depth first search algorithm in supercritical random graphs
JO  - The electronic journal of combinatorics
PY  - 2022
VL  - 29
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/10894/
DO  - 10.37236/10894
ID  - 10_37236_10894
ER  - 
%0 Journal Article
%A Sahar Diskin
%A Michael Krivelevich
%T On the performance of the depth first search algorithm in supercritical random graphs
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/10894/
%R 10.37236/10894
%F 10_37236_10894
Sahar Diskin; Michael Krivelevich. On the performance of the depth first search algorithm in supercritical random graphs. The electronic journal of combinatorics, Tome 29 (2022) no. 3. doi: 10.37236/10894

Cité par Sources :