On the performance of the depth first search algorithm in supercritical random graphs (Q2088713): Difference between revisions

Summary: We consider the performance of the Depth First Search (DFS) algorithm on the random graph \(G(n, \frac{1+\epsilon}{n})\), \(\epsilon>0\) a small constant. Recently, \textit{N. Enriquez} et al. [Random Struct. Algorithms 56, No. 2, 501--516 (2020; Zbl 1436.05096)] proved that the stack \(U\) of the DFS follows a specific scaling limit, reaching the maximal height of \((1+o_{\epsilon}(1))\epsilon^2n\). Here we provide a simple analysis for the typical length of a maximum path discovered by the DFS.