An approximation algorithm for maximum internal spanning tree

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

3 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)955-979
Journal / PublicationJournal of Combinatorial Optimization
Volume35
Issue number3
Online published15 Jan 2018
Publication statusPublished - Apr 2018

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. The discovered structure may be used to design even better approximation or parameterized algorithms for the problem in the future.

Research Area(s)

  • Approximation algorithms, Graph algorithms, Path-cycle covers, Spanning trees

Citation Format(s)

An approximation algorithm for maximum internal spanning tree. / Chen, Zhi-Zhong; Harada, Youta; Guo, Fei; Wang, Lusheng.

In: Journal of Combinatorial Optimization, Vol. 35, No. 3, 04.2018, p. 955-979.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review