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 \(\frac{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, \(\frac{13}{17}\)) with the same time complexity. Our new algorithm explores much deeper structure of the problem than the previous best. As our recent \(\frac{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.
L. Wang—Supported by NSFC (61373048) and GRF (CityU 123013) grants.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Binkele-Raible, D., Fernau, H., Gaspers, S., Liedloff, M.: Exact and parameterized algorithms for max internal spanning tree. Algorithmica 65(1), 95–128 (2013)
Chen, Z.-Z., Lin, G., Wang, L., Chen, Y.: Approximation Algorithms for the Maximum Weight Internal Spanning Tree Problem. CoRR, abs/1608.03299 (2016)
Hartvigsen, D.: Extensions of matching theory. Ph.D. thesis, Carnegie-Mellon University (1984)
Knauer, M., Spoerhase, J.: Better approximation algorithms for the maximum internal spanning tree problem. In: Dehne, F., Gavrilova, M., Sack, J.-R., Tóth, C.D. (eds.) WADS 2009. LNCS, vol. 5664, pp. 459–470. Springer, Heidelberg (2009). doi:10.1007/978-3-642-03367-4_40
Li, X., Zhu, D.: Approximating the maximum internal spanning tree problem via a maximum path-cycle cover. In: Ahn, H.-K., Shin, C.-S. (eds.) ISAAC 2014. LNCS, vol. 8889, pp. 467–478. Springer, Heidelberg (2014). doi:10.1007/978-3-319-13075-0_37
Li, W., Wang, J., Chen, J., Cao, Y.: A 2k-vertex kernel for maximum internal spanning tree. In: Dehne, F., Sack, J.-R., Stege, U. (eds.) WADS 2015. LNCS, vol. 9214, pp. 495–505. Springer, Heidelberg (2015). doi:10.1007/978-3-319-21840-3_41
Salamon, G., Wiener, G.: On finding spanning trees with few leaves. Inf. Process. Lett. 105(5), 164–169 (2008)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Chen, ZZ., Harada, Y., Guo, F., Wang, L. (2017). An Approximation Algorithm for Maximum Internal Spanning Tree. In: Poon, SH., Rahman, M., Yen, HC. (eds) WALCOM: Algorithms and Computation. WALCOM 2017. Lecture Notes in Computer Science(), vol 10167. Springer, Cham. https://doi.org/10.1007/978-3-319-53925-6_30
Download citation
DOI: https://doi.org/10.1007/978-3-319-53925-6_30
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-53924-9
Online ISBN: 978-3-319-53925-6
eBook Packages: Computer ScienceComputer Science (R0)