Approximation algorithms for the maximum weight internal spanning tree problem

Zhi-Zhong Chen; Guohui Lin; Lusheng Wang; Yong Chen; Dan Wang

doi:10.1007/978-3-319-62389-4_11

Approximation algorithms for the maximum weight internal spanning tree problem

Zhi-Zhong Chen
, Guohui Lin
, Lusheng Wang
, Yong Chen
, Dan Wang

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

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 the 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 13/17. The currently best approximation algorithm for MwIST only has a performance ratio 1/3−ϵ, for any ϵ > 0. In this paper, we present a simple algorithm based on a novel relationship between MwIST and the maximum weight matching, and show that it achieves a better approximation ratio of 1/2. When restricted to clawfree graphs, a special case been previously studied, we design a 7/12-approximation algorithm.

Original language	English
Title of host publication	Computing and Combinatorics : 23rd International Conference, COCOON 2017 Hong Kong, China, August 3–5, 2017 Proceedings
Editors	Yixin Cao, Jianer Chen
Publisher	Springer
Pages	124-136
ISBN (Electronic)	978-3-319-62389-4
ISBN (Print)	9783319623887
DOIs	https://doi.org/10.1007/978-3-319-62389-4_11
Publication status	Published - 3 Aug 2017
Event	23rd annual International Computing and Combinatorics Conference (COCOON' 17) - The Hong Kong Polytechnic University, Hong Kong, China Duration: 3 Aug 2017 → 5 Aug 2017 http://cocoon2017.comp.polyu.edu.hk/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer International Publishing AG
Volume	LNCS 10392
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	23rd annual International Computing and Combinatorics Conference (COCOON' 17)
Abbreviated title	COCOON' 17
Place	China
City	Hong Kong
Period	3/08/17 → 5/08/17
Internet address	http://cocoon2017.comp.polyu.edu.hk/

Research Keywords

Approximation algorithm
Maximum weight internal spanning tree
Maximum weight matching
Performance analysis

Access Output

10.1007/978-3-319-62389-4_11

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Chen, Z.-Z., Lin, G., Wang, L., Chen, Y., & Wang, D. (2017). Approximation algorithms for the maximum weight internal spanning tree problem. In Y. Cao, & J. Chen (Eds.), Computing and Combinatorics : 23rd International Conference, COCOON 2017 Hong Kong, China, August 3–5, 2017 Proceedings (pp. 124-136). (Lecture Notes in Computer Science; Vol. LNCS 10392). Springer . https://doi.org/10.1007/978-3-319-62389-4_11

@inproceedings{bed5dc72db3a48829a2367f38a702add,

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 the 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 13/17. The currently best approximation algorithm for MwIST only has a performance ratio 1/3−ϵ, for any ϵ > 0. In this paper, we present a simple algorithm based on a novel relationship between MwIST and the maximum weight matching, and show that it achieves a better approximation ratio of 1/2. When restricted to clawfree graphs, a special case been 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 = "2017",

month = aug,

day = "3",

doi = "10.1007/978-3-319-62389-4\_11",

language = "English",

isbn = "9783319623887",

series = "Lecture Notes in Computer Science",

publisher = "Springer ",

pages = "124--136",

editor = "Yixin Cao and Jianer Chen",

booktitle = "Computing and Combinatorics : 23rd International Conference, COCOON 2017 Hong Kong, China, August 3–5, 2017 Proceedings",

note = "23rd annual International Computing and Combinatorics Conference (COCOON' 17), COCOON' 17 ; Conference date: 03-08-2017 Through 05-08-2017",

url = "http://cocoon2017.comp.polyu.edu.hk/",

}

Chen, Z-Z, Lin, G, Wang, L, Chen, Y & Wang, D 2017, Approximation algorithms for the maximum weight internal spanning tree problem. in Y Cao & J Chen (eds), Computing and Combinatorics : 23rd International Conference, COCOON 2017 Hong Kong, China, August 3–5, 2017 Proceedings. Lecture Notes in Computer Science, vol. LNCS 10392, Springer , pp. 124-136, 23rd annual International Computing and Combinatorics Conference (COCOON' 17), Hong Kong, China, 3/08/17. https://doi.org/10.1007/978-3-319-62389-4_11

Approximation algorithms for the maximum weight internal spanning tree problem. / Chen, Zhi-Zhong; Lin, Guohui; Wang, Lusheng et al.
Computing and Combinatorics : 23rd International Conference, COCOON 2017 Hong Kong, China, August 3–5, 2017 Proceedings. ed. / Yixin Cao; Jianer Chen. Springer , 2017. p. 124-136 (Lecture Notes in Computer Science; Vol. LNCS 10392).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

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 - 2017/8/3

Y1 - 2017/8/3

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 the 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 13/17. The currently best approximation algorithm for MwIST only has a performance ratio 1/3−ϵ, for any ϵ > 0. In this paper, we present a simple algorithm based on a novel relationship between MwIST and the maximum weight matching, and show that it achieves a better approximation ratio of 1/2. When restricted to clawfree graphs, a special case been 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 the 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 13/17. The currently best approximation algorithm for MwIST only has a performance ratio 1/3−ϵ, for any ϵ > 0. In this paper, we present a simple algorithm based on a novel relationship between MwIST and the maximum weight matching, and show that it achieves a better approximation ratio of 1/2. When restricted to clawfree graphs, a special case been 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 - https://www.scopus.com/pages/publications/85028473531

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85028473531&origin=recordpage

U2 - 10.1007/978-3-319-62389-4_11

DO - 10.1007/978-3-319-62389-4_11

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9783319623887

T3 - Lecture Notes in Computer Science

SP - 124

EP - 136

BT - Computing and Combinatorics : 23rd International Conference, COCOON 2017 Hong Kong, China, August 3–5, 2017 Proceedings

A2 - Cao, Yixin

A2 - Chen, Jianer

PB - Springer

T2 - 23rd annual International Computing and Combinatorics Conference (COCOON' 17)

Y2 - 3 August 2017 through 5 August 2017

ER -

Chen ZZ, Lin G, Wang L, Chen Y, Wang D. Approximation algorithms for the maximum weight internal spanning tree problem. In Cao Y, Chen J, editors, Computing and Combinatorics : 23rd International Conference, COCOON 2017 Hong Kong, China, August 3–5, 2017 Proceedings. Springer . 2017. p. 124-136. (Lecture Notes in Computer Science). Epub 2017 Jul 1. doi: 10.1007/978-3-319-62389-4_11

Approximation algorithms for the maximum weight internal spanning tree problem

Abstract

Publication series

Conference

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this