Approximation Algorithms for the Maximum Weight Internal Spanning Tree Problem
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Pages (from-to) | 4167–4199 |
| Journal / Publication | Algorithmica |
| Volume | 81 |
| Issue number | 11-12 |
| Online published | 11 Dec 2018 |
| Publication status | Published - Nov 2019 |
Link(s)
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.
Research Area(s)
- Approximation algorithm, Maximum weight internal spanning tree, Maximum weight matching, Performance analysis
Citation Format(s)
Approximation Algorithms for the Maximum Weight Internal Spanning Tree Problem. / Chen, Zhi-Zhong; Lin, Guohui; Wang, Lusheng et al.
In: Algorithmica, Vol. 81, No. 11-12, 11.2019, p. 4167–4199.
In: Algorithmica, Vol. 81, No. 11-12, 11.2019, p. 4167–4199.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
