Back to Search
Start Over
A Simple 2-Approximation for Maximum-Leaf Spanning Tree.
- Source :
- International Journal of Foundations of Computer Science; Nov2023, Vol. 34 Issue 7, p795-805, 11p
- Publication Year :
- 2023
-
Abstract
- For an m -edge connected simple graph G , finding a spanning tree of G with the maximum number of leaves is MAXSNP-complete. The problem remains NP-complete even if G is planar and the maximal degree of G is at most four. Lu and Ravi gave the first known polynomial-time approximation algorithms with approximation factors 5 and 3. Later, they obtained a 3 -approximation algorithm that runs in near-linear time. The best known result is Solis-Oba, Bonsma, and Lowski's O (m) -time 2 -approximation algorithm. We show an alternative simple O (m) -time 2 -approximation algorithm whose analysis is simpler. This paper is dedicated to the cherished memory of our dear friend, Professor Takao Nishizeki. [ABSTRACT FROM AUTHOR]
- Subjects :
- SPANNING trees
APPROXIMATION algorithms
NP-complete problems
ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 01290541
- Volume :
- 34
- Issue :
- 7
- Database :
- Complementary Index
- Journal :
- International Journal of Foundations of Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 173182842
- Full Text :
- https://doi.org/10.1142/S0129054123420029