Depth-First Search performance in a random digraph with geometric outdegree distribution

2022/12/30 by Philippe Jacquet, Svante Janson, Jacquet, Philippe +1
Computer Science · Physics and Astronomy · #Advanced Graph Theory Research #Complex Network Analysis Techniques #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.2212.14865

openalex publication_date 2022/12/30 · openalex created_date 2023/01/06 · openalex updated_date 2026/07/28

Abstract

We present an analysis of the depth-first search algorithm in a random digraph model with independent outdegrees having a geometric distribution. The results include asymptotic results for the depth profile of vertices, the height (maximum depth) and average depth, the number of trees in the forest, the size of the largest and second-largest trees, and the numbers of arcs of different types in the depth-first jungle. Most results are first order. For the height we show an asymptotic normal distribution. This analysis proposed 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.

Related

• On the Performance of the Depth First Search Algorithm in Supercritical Random Graphs
• On Knuth's conjecture for back and forward arcs in Depth First Search in a random digraph with geometric outdegree distribution
• Depth-first search in split-by-edges trees
• On a conjecture of Knuth about forward and back arcs
• Depth First Exploration of a Configuration Model