On the performance of the depth first search algorithm in supercritical random graphs

DOI10.37236/10894zbMath1498.05261arXiv2111.07345OpenAlexW3214230297MaRDI QIDQ2088713

Michael Krivelevich, Sahar Diskin

Publication date: 6 October 2022

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

spanning treeanalysis of the performance

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Site percolation on pseudo‐random graphs ⋮ Depth-first search performance in a random digraph with geometric outdegree distribution

Cites Work

• Unnamed Item
• The phase transition in random graphs: A simple proof
• Introduction to Random Graphs
• Cycles in a random graph near the critical point
• Limiting shape of the depth first search tree in an Erdős‐Rényi graph
• An Improved Upper Bound on the Length of the Longest Cycle of a Supercritical Random Graph

This page was built for publication: On the performance of the depth first search algorithm in supercritical random graphs