Back to Search
Start Over
A [formula omitted]-approximation algorithm for the Maximum Internal Spanning Tree Problem.
- Source :
-
Journal of Computer & System Sciences . Jun2021, Vol. 118, p131-140. 10p. - Publication Year :
- 2021
-
Abstract
- In this paper, we study the Maximum Internal Spanning Tree Problem (MIST). Given an undirected simple graph G , the task for the Maximum Internal Spanning Tree problem is to find a spanning tree of G with maximum number of internal vertices. We present an approximation algorithm with performance ratio 4 3 , which improves upon the best known performance ratio 3 2. Our algorithm benefits from a new observation for bounding the number of internal vertices of a spanning tree. We can also give an example to show that the performance ratio 4 3 is actually tight for this algorithm. Finally, we show that MIST is Max-SNP-hard. [ABSTRACT FROM AUTHOR]
- Subjects :
- *SPANNING trees
*UNDIRECTED graphs
*APPROXIMATION algorithms
*ALGORITHMS
*AEROSOLS
Subjects
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 118
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 148450513
- Full Text :
- https://doi.org/10.1016/j.jcss.2021.01.001