Depth-first search performance in random digraphs

DOI10.4230/LIPICS.AOFA.2024.30MaRDI QIDQ6865664zbMATH OpenFDO

Authors Philippe Jacquet, Svante Janson

Publication date 30 January 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.AOFA.2024.30

zbMATH Keywords

analysis of algorithmsdepth first searchrandom digraph

Mathematics Subject Classification ID

Analysis of algorithms (68W40)

Cites work

• A random walk approach to Galton-Watson trees
• Branching processes in Lévy processes: The exploration process
• Depth first exploration of a configuration model
• Depth-first search performance in a random digraph with geometric outdegree distribution
• Limiting shape of the depth first search tree in an Erdős-Rényi graph
• On the performance of the depth first search algorithm in supercritical random graphs
• The phase transition in random graphs: a simple proof

This page was built for publication: Depth-first search performance in random digraphs

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