On the Performance of the Depth First Search Algorithm in Supercritical Random Graphs

2021/11/14 by Diskin, Sahar, Krivelevich, Michael · 1 citation
#05C80 #60C05 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2111.07345

Abstract

We consider the performance of the Depth First Search (DFS) algorithm on the random graph G(n,(1+ε)/(n)), ε>0 a small constant. Recently, Enriquez, Faraud and Ménard [2] proved that the stack U of the DFS follows a specific scaling limit, reaching the maximal height of (1+o_ε(1))ε²n. Here we provide a simple analysis for the typical length of a maximum path discovered by the DFS.

Cited by

• Ethereum Conflicts Graphed

Related

• Depth First Exploration of a Configuration Model
• Incremental DFS algorithms: a theoretical and experimental study
• Depth-First Search performance in a random digraph with geometric outdegree distribution
• Parallel Complexity of Depth-First-Search and Maximal path in restricted graph classes
• Short proofs for long induced paths