# The Full Degree Spanning Tree Problem

 dc.contributor.author Bhatia, Randeep en_US dc.contributor.author Khuller, Samir en_US dc.contributor.author Pless, Robert en_US dc.contributor.author Sussmann, Yoram en_US dc.date.accessioned 2004-05-31T21:07:51Z dc.date.available 2004-05-31T21:07:51Z dc.date.created 1998-10 en_US dc.date.issued 1998-10-15 en_US dc.identifier.uri http://hdl.handle.net/1903/497 dc.description.abstract The 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.extent 326854 bytes dc.format.mimetype application/postscript dc.language.iso en_US dc.relation.ispartofseries UM Computer Science Department; CS-TR-3931 en_US dc.title The Full Degree Spanning Tree Problem en_US dc.type Technical Report en_US dc.relation.isAvailableAt Digital Repository at the University of Maryland en_US dc.relation.isAvailableAt University of Maryland (College Park, Md.) en_US dc.relation.isAvailableAt Tech Reports in Computer Science and Engineering en_US dc.relation.isAvailableAt Computer Science Department Technical Reports en_US
﻿