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.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.identifier.uri | http://hdl.handle.net/1903/497 | |
| dc.language.iso | 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 |
| 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 |