A branch vertex in a tree is a vertex of degree at least three. We study the NP-hard problem of constructing spanning trees with as few branch vertices as possible. This problem generalizes the famous Hamiltonian Path problem which corresponds to the case of no vertices having degree three or more. It has been extensively studied in the literature and has important applications in network design and optimization. In this paper, we study the problem of finding a spanning tree with the minimum number of branch vertices in graphs of bounded neighborhood diversity. Neighborhood diversity, a generalization of vertex cover to dense graphs, plays an important role in the design of algorithms for such graphs.
Spanning Trees with Few Branch Vertices in Graphs of Bounded Neighborhood Diversity
Gargano L.;Rescigno A. A.
2023-01-01
Abstract
A branch vertex in a tree is a vertex of degree at least three. We study the NP-hard problem of constructing spanning trees with as few branch vertices as possible. This problem generalizes the famous Hamiltonian Path problem which corresponds to the case of no vertices having degree three or more. It has been extensively studied in the literature and has important applications in network design and optimization. In this paper, we study the problem of finding a spanning tree with the minimum number of branch vertices in graphs of bounded neighborhood diversity. Neighborhood diversity, a generalization of vertex cover to dense graphs, plays an important role in the design of algorithms for such graphs.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
