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)