[{"dc":{"rights":["info:eu-repo/semantics/closedAccess"],"title":["Bounded degree spanning trees"],"description":["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$."],"language":["eng"],"source":["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"],"identifier":["https://ris.uni-paderborn.de/record/19869"],"date":["1997"],"type":["info:eu-repo/semantics/conferenceObject","doc-type:conferenceObject","text"],"creator":["Czumaj, Artur","Strothmann, Willy-B."],"relation":["info:eu-repo/semantics/altIdentifier/doi/10.1007/3-540-63397-9_9","info:eu-repo/semantics/altIdentifier/issn/0302-9743","info:eu-repo/semantics/altIdentifier/issn/1611-3349","info:eu-repo/semantics/altIdentifier/isbn/9783540633976","info:eu-repo/semantics/altIdentifier/isbn/9783540695363"]},"author":[{"first_name":"Artur","last_name":"Czumaj"},{"last_name":"Strothmann","first_name":"Willy-B."}],"_version":4,"publication_identifier":{"issn":[],"isbn":[]},"dini_type":"doc-type:conferenceObject","publication_status":"published","creator":{"id":"15415","login":"koala"},"department":[{"tree":[{"_id":"7"},{"_id":"34"},{"_id":"44"},{"_id":"43"}],"_id":"63"}],"language":[{}],"date_updated":"2020-10-05T07:17:44Z","citation":{"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.","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","ieee":"A. Czumaj and W.-B. Strothmann, “Bounded degree spanning trees,” in *Proceedings of the Fifth Annual European Symposium on Algorithms (ESA’97)*, 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.","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} }"},"user_id":"15415","status":"public","publication":"Proceedings of the Fifth Annual European Symposium on Algorithms (ESA'97)","type":"conference","uri_base":"https://ris.uni-paderborn.de","message":" #HNIID-1532","abstract":[{"lang":"eng"}],"date_created":"2020-10-05T07:13:42Z","_id":"19869"}]