EUVIMEDEUVIMED entdecken
Crossref

BFS versus DFS for Fixed-Level Targets in Ordered Trees

Stoyan Dimitrov, Martin Minchev, Yan Zhuang

SIAM Journal on Discrete Mathematics · 31.12.2026 · 40 (4) · 1913-1945

DOI: 10.1137/25m1760891 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 13.11.2026. Verfasst von Stoyan Dimitrov und 2 weiteren Autor:innen. Die Arbeit nennt 39 Literaturangaben. Gefördert von: AMS-Simons Travel Grant, European Union NextGenerationEU, National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We find the average time complexity of the breadth-first search (BFS) and the depth-first search (DFS) algorithms, when one searches for a target node selected uniformly at random among all nodes at level [Formula: see text] in the set of ordered trees with [Formula: see text] edges. Intuition suggests that on average BFS must be asymptotically faster than DFS if and only if [Formula: see text], as a function of [Formula: see text], is below a certain threshold. We confirm this intuition by showing that there exists a unique constant [Formula: see text], such that in expectation BFS is asymptotically faster than DFS if and only if [Formula: see text]. This gives us a practical rule to select between the two algorithms, even when we do not know the exact value of [Formula: see text], but only an estimate of it. Furthermore, we find the asymptotic average time complexity of BFS in the given setting for an arbitrary class of Galton–Watson trees, which includes ordered trees, binary trees, and other popular classes. We use results on the occupation measure of Brownian excursions, as well as combinatorial identities related to lattice paths. Finally, we consider the simple truncated DFS algorithm, which can be shown easily to be asymptotically faster than both BFS and DFS when [Formula: see text] is known in advance. We show that in fact its asymptotic time complexity is [Formula: see text] of the asymptotic complexity of BFS, when [Formula: see text] for any constant [Formula: see text]. Several further questions are also raised.

Förderung

  • AMS-Simons Travel Grant
  • European Union NextGenerationEU
  • National Science Foundation

Zitieren

APA

Dimitrov, S., Minchev, M., & Zhuang, Y. (2026). BFS versus DFS for Fixed-Level Targets in Ordered Trees. SIAM Journal on Discrete Mathematics, 40(4), 1913-1945. https://doi.org/10.1137/25m1760891

Vancouver

Dimitrov S, Minchev M, Zhuang Y. BFS versus DFS for Fixed-Level Targets in Ordered Trees. SIAM Journal on Discrete Mathematics. 2026;40(4):1913-1945. doi:10.1137/25m1760891

BibTeX
@article{Dimitrov2026,
  author = {Dimitrov, Stoyan and Minchev, Martin and Zhuang, Yan},
  title = {BFS versus DFS for Fixed-Level Targets in Ordered Trees},
  journal = {SIAM Journal on Discrete Mathematics},
  year = {2026},
  volume = {40},
  number = {4},
  pages = {1913--1945},
  doi = {10.1137/25m1760891}
}
Kostenlos starten →