---
_id: '19869'
abstract:
- lang: eng
text: 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$.
author:
- first_name: Artur
full_name: Czumaj, Artur
last_name: Czumaj
- first_name: Willy-B.
full_name: Strothmann, Willy-B.
last_name: Strothmann
citation:
ama: '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'
apa: Czumaj, A., & Strothmann, W.-B. (1997). Bounded degree spanning trees.
In *Proceedings of the Fifth Annual European Symposium on Algorithms (ESA’97)*.
https://doi.org/10.1007/3-540-63397-9_9
bibtex: '@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-B.}, year={1997} }'
chicago: Czumaj, Artur, and Willy-B. 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.
ieee: A. Czumaj and W.-B. Strothmann, “Bounded degree spanning trees,” in *Proceedings
of the Fifth Annual European Symposium on Algorithms (ESA’97)*, 1997.
mla: Czumaj, Artur, and Willy-B. 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.
short: 'A. Czumaj, W.-B. Strothmann, in: Proceedings of the Fifth Annual European
Symposium on Algorithms (ESA’97), 1997.'
date_created: 2020-10-05T07:13:42Z
date_updated: 2020-10-05T07:17:44Z
department:
- _id: '63'
doi: 10.1007/3-540-63397-9_9
language:
- iso: eng
publication: Proceedings of the Fifth Annual European Symposium on Algorithms (ESA'97)
publication_identifier:
isbn:
- '9783540633976'
- '9783540695363'
issn:
- 0302-9743
- 1611-3349
publication_status: published
status: public
title: Bounded degree spanning trees
type: conference
user_id: '15415'
year: '1997'
...