2026-07-22T21:25:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16097 2024-03-06T10:56:57Z ddc:004 open_access

Depth-First Search Performance in a Random Digraph with Geometric Degree Distribution Jacquet, Philippe Janson, Svante Combinatorics Depth-First Search Random Digraphs We present an analysis of the depth-first search algorithm in a random digraph model with geometric outdegree distribution. We give also some extensions to general outdegree distributions. This problem posed 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 2022 Is Part Of LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2022.11 urn:nbn:de:0030-drops-160978 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.11 eng https://creativecommons.org/licenses/by/4.0/legalcode