Metraipolis › archive › dc_dab4b5abe899

Generalized Graph Search Trees — arXiv:2609.08625

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.08625
License (as archived)
CC0-1.0
Archived
2026-10-16T15:31:56.135Z
SHA-256 of the archived text
4daaae2fe260c6d0def0b5288e0ef9a9e268885fb6e5a9b9c561db5ae98e2a54
Stable URL of this page
https://metraipolis.com/documento/dc_dab4b5abe899

How to cite

Generalized Graph Search Trees — arXiv:2609.08625 — arXiv (en), https://arxiv.org/abs/2609.08625 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_dab4b5abe899 (Metraipolis archive dc_dab4b5abe899, sha256 4daaae2fe260c6d0def0b5288e0ef9a9e268885fb6e5a9b9c561db5ae98e2a54)
BibTeX
@misc{dcdab4b5abe899,
  title = {Generalized Graph Search Trees — arXiv:2609.08625},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.08625},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_dab4b5abe899; sha256 4daaae2fe260c6d0def0b5288e0ef9a9e268885fb6e5a9b9c561db5ae98e2a54},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.08625. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Graph search algorithms and their corresponding graph search trees are commonly used in algorithmic graph theory. In recent years, the recognition problem of these graph search trees has received significant attention. So far, the research has focused on two types of search trees: first-in trees that behave like BFS-trees and last-in trees that behave like DFS-trees. The search tree paradigms differ from each other by the parent a vertex is connected to. In first-in trees, it is the first visited neighbor, while in last-in trees it is the last neighbor visited before that vertex. Here, we will generalize these concepts of graph search trees by allowing every preceding neighbor of a vertex to be the parent. We study the complexity of the recognition problem of these generalized graph search trees. We present NP-completeness proofs for most searches. We also show that the problem is trivial for Generic Search and polynomial-time solvable for several searches on bipartite graphs and chordal graphs. We also study the question how fixing the start vertex influences the complexity of the problem.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-09 in cs.DS).
Categorie arXiv: Discrete Mathematics (cs.DM) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.08625 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T15:15:08.365Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).