On the performance of the depth first search algorithm in supercritical random graphs (Q2088713): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 05:49, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the performance of the depth first search algorithm in supercritical random graphs |
scientific article |
Statements
On the performance of the depth first search algorithm in supercritical random graphs (English)
0 references
6 October 2022
0 references
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.
0 references
spanning tree
0 references
analysis of the performance
0 references