Show simple item record

The Full Degree Spanning Tree Problem

dc.contributor.authorBhatia, Randeepen_US
dc.contributor.authorKhuller, Samiren_US
dc.contributor.authorPless, Roberten_US
dc.contributor.authorSussmann, Yoramen_US
dc.description.abstractThe full degree spanning tree problem is defined as follows: given a connected graph $G=(V,E)$ find a spanning tree $T$ so as to maximize the number of vertices whose degree in $T$ is the same as in $G$ (these are called vertices of ``full'' degree). We show that this problem is NP-hard. We also present almost {\em optimal} approximation algorithms for it assuming $coR \neq NP$. For the case of general graphs our approximation factor is $\Theta(\sqrt{n})$. Using H{\aa}stad's result on the hardness of approximating clique, we can show that if there is a polynomial time approximation algorithm for our problem with a factor of $O(n^{\frac{1}{2}-\epsilon})$ then $coR=NP$. For the case of planar graphs, we present a polynomial time approximation scheme. Additionally, we present some experimental results comparing our algorithm to the previous heuristic used for this problem. (Also cross-referenced as UMIACS 98-47)en_US
dc.format.extent326854 bytes
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-3931en_US
dc.titleThe Full Degree Spanning Tree Problemen_US
dc.typeTechnical Reporten_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtComputer Science Department Technical Reportsen_US

Files in this item


This item appears in the following Collection(s)

Show simple item record