Bounded degree spanning trees

A. Czumaj, W.-B. Strothmann, in: Proceedings of the Fifth Annual European Symposium on Algorithms (ESA’97), 1997.

Download
No fulltext has been uploaded.
Conference Paper | Published | English
Author
Czumaj, Artur; Strothmann, Willy-Bernhard
Abstract
Given a connected graph $G$, let a $dT$-spanning tree of $G$ be a spanning tree of $G$ of maximum degree bounded by $dT$. It is well known that for each $dT ge 2$ the problem of deciding whether a connected graph has a $dT$-spanning tree is NP-complete. In this paper we investigate this problem when additionally connectivity and maximum degree of the graph are given. A complete characterization of this problem for 2- and 3-connected graphs, for planar graphs, and for $dT=2$ is provided. Our first result is that given a biconnected graph of maximum degree $2dT-2$, we can find its $dT$-spanning tree in time $O(m+n^3/2)$. For graphs of higher connectivity we design a polynomial-time algorithm that finds a $dT$-spanning tree in any $k$-connected graph of maximum degree $k(dT-2)+2$. On the other hand, we prove that deciding whether a $k$-connected graph of maximum degree $k(dT-2)+3$ has a $dT$-spanning tree is NP-complete, provided $k le 3$. For arbitrary $k ge 3$ we show that verifying whether a $k$-connected graph of maximum degree $k(dT-1)$ has a $dT$-spanning tree is NP-complete. In particular, we prove that the Hamiltonian path (cycle) problem is NP-complete for $k$-connected $k$-regular graphs, if $k>2$. This extends the well known result for $k=3$ and fully characterizes the case $dT=2$. For planar graphs it is NP-complete to decide whether a $k$-connected planar graph of maximum degree $dG$ has a $dT$-spanning tree for $k=1$ and $dG > dT ge 2$, for $k=2$ and $dG > 2(dT-1) ge 2$, and for $k=3$ and $dG > dT = 2$. On the other hand, we show how to find in polynomial (linear or almost linear) time a $dT$-spanning tree for all other parameters of $k$, $dG$, and $dT$.
Publishing Year
Proceedings Title
Proceedings of the Fifth Annual European Symposium on Algorithms (ESA'97)
LibreCat-ID

Cite this

Czumaj A, Strothmann W-B. Bounded degree spanning trees. In: Proceedings of the Fifth Annual European Symposium on Algorithms (ESA’97). ; 1997. doi:10.1007/3-540-63397-9_9
Czumaj, A., & Strothmann, W.-B. (1997). Bounded degree spanning trees. Proceedings of the Fifth Annual European Symposium on Algorithms (ESA’97). https://doi.org/10.1007/3-540-63397-9_9
@inproceedings{Czumaj_Strothmann_1997, title={Bounded degree spanning trees}, DOI={10.1007/3-540-63397-9_9}, booktitle={Proceedings of the Fifth Annual European Symposium on Algorithms (ESA’97)}, author={Czumaj, Artur and Strothmann, Willy-Bernhard}, year={1997} }
Czumaj, Artur, and Willy-Bernhard Strothmann. “Bounded Degree Spanning Trees.” In Proceedings of the Fifth Annual European Symposium on Algorithms (ESA’97), 1997. https://doi.org/10.1007/3-540-63397-9_9.
A. Czumaj and W.-B. Strothmann, “Bounded degree spanning trees,” 1997, doi: 10.1007/3-540-63397-9_9.
Czumaj, Artur, and Willy-Bernhard Strothmann. “Bounded Degree Spanning Trees.” Proceedings of the Fifth Annual European Symposium on Algorithms (ESA’97), 1997, doi:10.1007/3-540-63397-9_9.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar
ISBN Search