LIPIcs.AofA.2022.11.pdf
- Filesize: 1.03 MB
- 15 pages
Document
Depth-First Search Performance in a Random Digraph with Geometric Degree Distribution
Authors
Philippe Jacquet 
,
Svante Janson
-
Part of:
Volume:
33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-06-08
File
Document Identifiers
Author Details
Acknowledgements
We thank Donald Knuth for posing us questions and conjectures that led to the present paper.
Cite As Get BibTex
Philippe Jacquet and Svante Janson. Depth-First Search Performance in a Random Digraph with Geometric Degree Distribution. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.AofA.2022.11
Abstract
We present an analysis of the depth-first search algorithm in a random digraph model with geometric outdegree distribution. We give also some extensions to general outdegree distributions. This problem posed by Donald Knuth in his next to appear volume of The Art of Computer Programming gives interesting insight in one of the most elegant and efficient algorithm for graph analysis due to Tarjan.
Subject Classification
ACM Subject Classification
- Theory of computation → Graph algorithms analysis
Keywords
- Combinatorics
- Depth-First Search
- Random Digraphs
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
David Aldous. Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Probab., 25(2):812-854, 1997.
- Sahar Diskin and Michael Krivelevich. On the performance of the Depth First Search algorithm in supercritical random graphs. arXiv preprint, 2021. URL: http://arxiv.org/abs/2111.07345.
-
Nathanaël Enriquez, Gabriel Faraud, and Laurent Ménard. Limiting shape of the depth first search tree in an Erdős-Rényi graph. Random Structures Algorithms, 56(2):501-516, 2020.
- Svante Janson and Philippe Jacquet. Depth-First Search performance in random digraphs. preprint, 2022. URL: https://hal.archives-ouvertes.fr/hal-03537124.
- Donald E. Knuth. The Art of Computer Programming, Section 7.4.1.2, 2022. (Preliminary draft, 13 February 2022). URL: http://cs.stanford.edu/~knuth/fasc12a.ps.gz.
-
Michael Krivelevich and Benny Sudakov. The phase transition in random graphs: a simple proof. Random Structures Algorithms, 43(2):131-138, 2013.