Approximation Algorithms for the Maximum Weight Internal Spanning Tree Problem

作     者：Chen, Zhi-Zhong Lin, Guohui Wang, Lusheng Chen, Yong Wang, Dan 

作者机构：Tokyo Denki Univ Div Informat Syst Design Hatoyama Saitama 3500394 Japan Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada City Univ Hong Kong Dept Comp Sci 83 Tat Chee Ave Kowloon Hong Kong Peoples R China City Univ Hong Kong Shenzhen Res Inst Shenzhen Hitech Ind Pk Shenzhen Peoples R China Hangzhou Dianzi Univ Inst Operat Res & Cybernet Hangzhou 310018 Zhejiang Peoples R China 

出 版 物：《ALGORITHMICA》 (算法)

年 卷 期：2019年第81卷第11-12期

页      面：4167-4199页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Ministry of Education, Culture, Sports, Science and Technology of Japan NSERC Canada NSFC [61672323, 11771114, 11571252] Research Grants Council of the Hong Kong Special Administrative Region, China [CityU 11256116] China Scholarship Council Grants-in-Aid for Scientific Research Funding Source: KAKEN 

主　　题：Maximum weight internal spanning tree Maximum weight matching Approximation algorithm Performance analysis 

摘      要：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-E, for any E0. 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.