Full degree spanning tree problem

Randeep Bhatia*, Samir Khuller, Robert Pless, Yoram J. Sussmann

*Corresponding author for this work

Research output: Contribution to conferencePaperpeer-review

7 Scopus citations

Abstract

The problem of computing a spanning tree T in a connected graph G so as to maximize the number of vertices of full degree is studied. This problem is NP-hard even when restricted to planar graphs by a reduction from the Maximum Independent Set problem. Approximation algorithms, which have a polynomial running time and produce a suboptimal solution, are considered for the problem.

Original languageEnglish (US)
StatePublished - Jan 1 1999
EventProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA
Duration: Jan 17 1999Jan 19 1999

Other

OtherProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms
CityBaltimore, MD, USA
Period1/17/991/19/99

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Full degree spanning tree problem'. Together they form a unique fingerprint.

Cite this