Depth-First Search Performance in a Random Digraph with Geometric Degree Distribution

Authors Philippe Jacquet , Svante Janson



PDF
Thumbnail PDF

File

LIPIcs.AofA.2022.11.pdf
  • Filesize: 1.03 MB
  • 15 pages

Document Identifiers

Author Details

Philippe Jacquet
  • Inria Saclay Ile de France, France
Svante Janson
  • Department of Mathematics, Uppsala University, Uppsala, Sweden

Acknowledgements

We thank Donald Knuth for posing us questions and conjectures that led to the present paper.

Cite AsGet 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)
    0
    PDF Downloads

References

  1. David Aldous. Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Probab., 25(2):812-854, 1997. Google Scholar
  2. 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.
  3. 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. Google Scholar
  4. Svante Janson and Philippe Jacquet. Depth-First Search performance in random digraphs. preprint, 2022. URL: https://hal.archives-ouvertes.fr/hal-03537124.
  5. 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.
  6. Michael Krivelevich and Benny Sudakov. The phase transition in random graphs: a simple proof. Random Structures Algorithms, 43(2):131-138, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail