TY - JOUR
T1 - Approximation Algorithms for the Maximum Weight Internal Spanning Tree Problem
AU - Chen, Zhi-Zhong
AU - Lin, Guohui
AU - Wang, Lusheng
AU - Chen, Yong
AU - Wang, Dan
PY - 2019/11
Y1 - 2019/11
N2 - 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.
AB - 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.
KW - Approximation algorithm
KW - Maximum weight internal spanning tree
KW - Maximum weight matching
KW - Performance analysis
UR - http://www.scopus.com/inward/record.url?scp=85058235451&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85058235451&origin=recordpage
U2 - 10.1007/s00453-018-00533-w
DO - 10.1007/s00453-018-00533-w
M3 - RGC 21 - Publication in refereed journal
VL - 81
SP - 4167
EP - 4199
JO - Algorithmica
JF - Algorithmica
SN - 0178-4617
IS - 11-12
ER -