Limiting shape of the depth first search tree in an Erdős‐Rényi graph

DOI10.1002/RSA.20878zbMATH Open1436.05096arXiv1704.00696OpenAlexW3105352506MaRDI QIDQ5113947FDOQ5113947

Nathanaël Enriquez, Gabriel Faraud, L. Ménard

Publication date: 19 June 2020

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: We show that the profile of the tree constructed by the Depth First Search Algorithm in the giant component of an ErdH{o}s-R'enyi graph with $N$ vertices and connection probability $c/N$ converges to an explicit deterministic shape. This makes it possible to exhibit a long non-intersecting path of length $left(h{o}_c-fracmathrm{Li}_2(h{o}_c)cight)imesN$, where $h{o}_c$ is the density of the giant component.

Full work available at URL: https://arxiv.org/abs/1704.00696

zbMATH Keywords

depth first search algorithmErdős-Rényi graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cited In (6)

• On depth first search trees in \(m\)-out digraphs
• Depth first exploration of a configuration model
• Chain-referral sampling on stochastic block models
• Respondent-driven sampling on sparse Erdös-Rényi graphs
• On the performance of the depth first search algorithm in supercritical random graphs
• Depth-first search performance in a random digraph with geometric outdegree distribution

This page was built for publication: Limiting shape of the depth first search tree in an Erdős‐Rényi graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5113947)