2026-08-19T07:30:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20465 2024-07-18T12:12:43Z ddc:004 open_access

Depth-First Search Performance in Random Digraphs Jacquet, Philippe Janson, Svante Depth First Search random digraph Analysis of Algorithms We present an analysis of the depth-first search algorithm in a random digraph model with independent outdegrees having an arbitrary distribution with finite variance. The results include asymptotics for the distribution of the stack index and depths of the search. The search yields a series of trees of finite size before and after the exploration of a giant tree. Our analysis mainly concerns the giant tree. Most results are first order. This analysis proposed by Donald Knuth in his next to appear volume of The Art of Computer Programming gives interesting insight in one of the most elegant and efficient algorithm for graph analysis due to Tarjan. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Philippe Jacquet and Svante Janson 2024 Is Part Of LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2024.30 urn:nbn:de:0030-drops-204655 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.30 eng https://creativecommons.org/licenses/by/4.0/legalcode