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: https://drops.dagstuhl.de/opus/volltexte/2022/16097/
Go to the corresponding LIPIcs Volume Portal


Jacquet, Philippe ; Janson, Svante

Depth-First Search Performance in a Random Digraph with Geometric Degree Distribution

pdf-format:
LIPIcs-AofA-2022-11.pdf (1 MB)


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


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI