Aug 2026· Journal of Graph Algorithms and Applications· Vol 30, pp. 339-362· 0 citations· 31 references
TL;DR
It is proved that shortest path tree graphs are hamiltonian, and an optimal linear-time algorithm for reconfiguration in shortest path tree graphs is provided, providing an optimal linear-time algorithm for reconfiguration in shortest path tree graphs.
Abstract
Flip graphs encode the structure of feasible transformations between combinatorial objects, making them a fundamental tool in reconfiguration problems. Tree graphs, which are flip graphs whose nodes represent the spanning trees of a graph, have received significant attention due to their algorithmic and structural properties. In this paper, we introduce new variations of tree graphs by restricting the spanning trees to shortest path trees, breadth-first search (BFS) trees, and depth-first search (DFS) trees. We prove that shortest path tree graphs are hamiltonian. Given any graph $G$, we present an algorithm that finds a hamiltonian cycle in its corresponding shortest path tree graph. We show that BFS-tree graphs and DFS-tree graphs are not necessarily connected. We establish some necessary conditions for the connectivity of BFS-tree and DFS-tree graphs. We provide an optimal linear-time algorithm for reconfiguration in shortest path tree graphs. Finally, we derive some bounds on the chromatic numbers of these new variations of tree graphs.
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.
The E2 Algorithm for constructing the Hamiltonian cycle in an arbitrary graph without edges’ weights is proposed and whether some general graphs are Hamiltonian is shown, to prove the correctness of the method.
Fatih Okumuş, A. Karadoğan· Fırat Üniversitesi Mühendisl...· 0 citations
It is shown that bidirectional Dijkstra is still instance-optimal on simple undirected weighted graphs under the order-oblivious model, where incident edges are given in a random order, and under the order-dependent model, where bidirectional Dijkstra is not instance-optimal.
Christian Bertram, Mads Vestergaard Jensen, Mikkel Thorup et al.· 0 citations
Under the APSP conjecture, no algorithm solves the narrow core in O ( m √ n polylog( nC )) time for all polynomially bounded integer costs: the decomposition confines the known hardness of 2-SP to a small, explicitly described class of detours.
A deterministic fully dynamic algorithm that simultaneously maintains SCCs and reachability in directed graphs and significantly outperforms repeated offline recomputation in practical scenarios is presented.
Gregory Morse, Tamás Kozsik· Annales Mathematicae et Info...· 0 citations
It is proved that the classical cut property always produces a minimum spanning tree of a connected graph, and may be useful for large weighted networks such as communication networks, wiring connections, and transportation networks.
H. Bhapkar, Rezwan Ul Shaban, S. Mir et al.· Journal of the Nigerian Soci...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
