@article{4baab9a90851473bb69994715db87393, title = "Approximation Algorithms for the Maximum Weight Internal Spanning Tree Problem", abstract = "Given a vertex-weighted connected graph G = (V, E), the maximum weight internal spanning tree (MwIST for short) problem asks for a spanning tree T of G such that the total weight of internal vertices in T is maximized. The unweighted variant, denoted as MIST, is NP-hard and APX-hard, and the currently best approximation algorithm has a proven performance ratio of 13/17. The currently best approximation algorithm for MwIST only has a performance ratio of 1/3−ϵ, for any ϵ > 0. In this paper, we present a simple algorithm based on a novel relationship between MwIST and maximum weight matching, and show that it achieves a significantly better approximation ratio of 1/2. When restricted to claw-free graphs, a special case previously studied, we design a 7/12-approximation algorithm.", keywords = "Approximation algorithm, Maximum weight internal spanning tree, Maximum weight matching, Performance analysis", author = "Zhi-Zhong Chen and Guohui Lin and Lusheng Wang and Yong Chen and Dan Wang", year = "2019", month = nov, doi = "10.1007/s00453-018-00533-w", language = "English", volume = "81", pages = "4167–4199", journal = "Algorithmica", issn = "0178-4617", publisher = "Springer", number = "11-12", }