License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2022.11
URN: urn:nbn:de:0030-drops-160978
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16097/
Jacquet, Philippe ;
Janson, Svante
Depth-First Search Performance in a Random Digraph with Geometric Degree Distribution
Abstract
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.
BibTeX - Entry
@InProceedings{jacquet_et_al:LIPIcs.AofA.2022.11,
author = {Jacquet, Philippe and Janson, Svante},
title = {{Depth-First Search Performance in a Random Digraph with Geometric Degree Distribution}},
booktitle = {33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
pages = {11:1--11:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-230-3},
ISSN = {1868-8969},
year = {2022},
volume = {225},
editor = {Ward, Mark Daniel},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16097},
URN = {urn:nbn:de:0030-drops-160978},
doi = {10.4230/LIPIcs.AofA.2022.11},
annote = {Keywords: Combinatorics, Depth-First Search, Random Digraphs}
}
|
Keywords: |
|
Combinatorics, Depth-First Search, Random Digraphs |
|
Collection: |
|
33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
08.06.2022 |
