@inproceedings{e5e55a7a213a40848be101ecb10f13dd,
title = "An approximation algorithm for maximum internal spanning tree",
abstract = "Given a graph G, the maximum internal spanning tree problem (MIST for short) asks for computing a spanning tree T of G such that the number of internal vertices in T is maximized. MIST has possible applications in the design of cost-efficient communication networks and water supply networks and hence has been extensively studied in the literature. MIST is NP-hard and hence a number of polynomial-time approximation algorithms have been designed for MIST in the literature. The previously best polynomial-time approximation algorithm for MIST achieves a ratio of 3/4. In this paper, we first design a simpler algorithm that achieves the same ratio and the same time complexity as the previous best. We then refine the algorithm into a new approximation algorithm that achieves a better ratio (namely, 13/17) with the same time complexity. Our new algorithm explores much deeper structure of the problem than the previous best. As our recent 1/2-approximation algorithm for the weighted version of the problem shows, the discovered structure may be used to design better algorithms for related problems.",
keywords = "Time Complexity , Approximation Algorithm, Span Tree, Tree Component , Edge Incident",
author = "Zhi-Zhong Chen and Youta Harada and Fei Guo and Lusheng Wang",
year = "2017",
month = mar,
doi = "10.1007/978-3-319-53925-6_30",
language = "English",
isbn = "9783319539249",
series = "Lecture Notes in Computer Science",
publisher = "Springer International Publishing ",
pages = "385--396",
editor = "Sheung-Hung Poon and Rahman, {Md. Saidur} and Hsu-Chun Yen",
booktitle = "WALCOM",
address = "Switzerland",
note = "11th International Conference and Workshops on Algorithms and Computation, WALCOM 2017 ; Conference date: 29-03-2017 Through 31-03-2017",
}