Full degree spanning tree problem

Randeep Bhatia; Samir Khuller; Robert Pless; Yoram J. Sussmann

Full degree spanning tree problem

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

^*Corresponding author for this work

Computer Science

Research output: Contribution to conference › Paper › peer-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 language	English (US)
State	Published - Jan 1 1999
Event	Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA Duration: Jan 17 1999 → Jan 19 1999

Other

Other	Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms
City	Baltimore, MD, USA
Period	1/17/99 → 1/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

@conference{8a7ff8cdab4f46cfa3300d4d061a14c2,

title = "Full degree spanning tree problem",

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.",

author = "Randeep Bhatia and Samir Khuller and Robert Pless and Sussmann, {Yoram J.}",

year = "1999",

month = jan,

day = "1",

language = "English (US)",

note = "Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 17-01-1999 Through 19-01-1999",

}

TY - CONF

T1 - Full degree spanning tree problem

AU - Bhatia, Randeep

AU - Khuller, Samir

AU - Pless, Robert

AU - Sussmann, Yoram J.

PY - 1999/1/1

Y1 - 1999/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0032785029&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032785029&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0032785029

T2 - Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 17 January 1999 through 19 January 1999

ER -