文摘
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.