[{"status":"public","language":[{}],"dc":{"identifier":["https://ris.uni-paderborn.de/record/19869"],"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"],"type":["info:eu-repo/semantics/conferenceObject","doc-type:conferenceObject","text","http://purl.org/coar/resource_type/c_5794"],"creator":["Czumaj, Artur","Strothmann, Willy-Bernhard"],"language":["eng"],"date":["1997"],"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"],"title":["Bounded degree spanning trees"],"rights":["info:eu-repo/semantics/closedAccess"],"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$."]},"publication_identifier":{"issn":[],"isbn":[]},"message":" #HNIID-1532","_id":"19869","citation":{"short":"A. Czumaj, W.-B. Strothmann, in: Proceedings of the Fifth Annual European Symposium on Algorithms (ESA’97), 1997.","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-Bernhard}, year={1997} }","chicago":"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.","ieee":"A. Czumaj and W.-B. Strothmann, “Bounded degree spanning trees,” 1997, doi: 10.1007/3-540-63397-9_9.","mla":"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.","apa":"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"},"creator":{"id":"15415","login":"koala"},"department":[{"_id":"63","tree":[{"_id":"7"},{"_id":"34"},{"_id":"44"},{"_id":"43"}]}],"abstract":[{"lang":"eng"}],"author":[{"last_name":"Czumaj","first_name":"Artur"},{"last_name":"Strothmann","first_name":"Willy-Bernhard"}],"publication_status":"published","user_id":"15415","date_updated":"2022-01-06T06:54:14Z","publication":"Proceedings of the Fifth Annual European Symposium on Algorithms (ESA'97)","dini_type":"doc-type:conferenceObject","uri_base":"https://ris.uni-paderborn.de","type":"conference","date_created":"2020-10-05T07:13:42Z"}]