EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Philippe Jacquet, Svante Janson

La Matematica · 01.03.2024 · 3 (1) · 262-292

DOI: 10.1007/s44007-024-00085-2 ↗

Kurz gefasst

Fachartikel in der Zeitschrift La Matematica, online erschienen am 01.03.2024. Verfasst von Philippe Jacquet und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 20 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Knut och Alice Wallenbergs Stiftelse.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We present an analysis of the depth-first search algorithm in a random digraph model with independent outdegrees having a geometric distribution. The results include asymptotic results for the depth profile of vertices, the height (maximum depth) and average depth, the number of trees in the forest, the size of the largest and second-largest trees, and the numbers of arcs of different types in the depth-first jungle. Most results are first order. For the height, we show an asymptotic normal distribution. 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.

Förderung

  • Knut och Alice Wallenbergs Stiftelse

Zitieren

APA

Jacquet, P., & Janson, S. (2024). Depth-First Search Performance in a Random Digraph with Geometric Outdegree Distribution. La Matematica, 3(1), 262-292. https://doi.org/10.1007/s44007-024-00085-2

Vancouver

Jacquet P, Janson S. Depth-First Search Performance in a Random Digraph with Geometric Outdegree Distribution. La Matematica. 2024;3(1):262-292. doi:10.1007/s44007-024-00085-2

BibTeX
@article{Jacquet2024,
  author = {Jacquet, Philippe and Janson, Svante},
  title = {Depth-First Search Performance in a Random Digraph with Geometric Outdegree Distribution},
  journal = {La Matematica},
  year = {2024},
  volume = {3},
  number = {1},
  pages = {262--292},
  doi = {10.1007/s44007-024-00085-2}
}
Kostenlos starten →