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

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl DOI arXiv
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 
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
@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

Cité par Sources :