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.date.accessioned2004-05-31T21:07:51Z
dc.date.available2004-05-31T21:07:51Z
dc.date.created1998-10en_US
dc.date.issued1998-10-15en_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.format.mimetypeapplication/postscript
dc.identifier.urihttp://hdl.handle.net/1903/497
dc.language.isoen_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
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-3931en_US
dc.titleThe Full Degree Spanning Tree Problemen_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 2 of 2
No Thumbnail Available
Name:
CS-TR-3931.ps
Size:
319.19 KB
Format:
Postscript Files
Loading...
Thumbnail Image
Name:
CS-TR-3931.pdf
Size:
238.08 KB
Format:
Adobe Portable Document Format
Description:
Auto-generated copy of CS-TR-3931.ps