A PTAS for node-weighted steiner tree in unit disk graphs

Xianyue Li; Xiao Hua Xu; Feng Zou; Hongwei Du; Pengjun Wan; Yuexuan Wang; Weili Wu

doi:10.1007/978-3-642-02026-1_4

A PTAS for node-weighted steiner tree in unit disk graphs

Xianyue Li^*
, Xiao Hua Xu
, Feng Zou
, Hongwei Du
, Pengjun Wan
, Yuexuan Wang
, Weili Wu

^*Corresponding author for this work

Lanzhou University
Illinois Institute of Technology
University of Texas at Dallas
Tsinghua University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

12 Scopus citations

Abstract

The node-weighted Steiner tree problem is a variation of classical Steiner minimum tree problem. Given a graph G=(V,E) with node weight function C:V→R⁺ and a subset X of V, the node-weighted Steiner tree problem is to find a Steiner tree for the set X such that its total weight is minimum. In this paper, we study this problem in unit disk graphs and present a (1+ε)-approximation algorithm for any ε>0, when the given set of vertices is c-local. As an application, we use node-weighted Steiner tree to solve the node-weighted connected dominating set problem in unit disk graphs and obtain a (5+ε)-approximation algorithm.

Original language	English
Title of host publication	Combinatorial Optimization and Applications - Third International Conference, COCOA 2009, Proceedings
Pages	36-48
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-642-02026-1_4
State	Published - 2009
Externally published	Yes
Event	3rd International Conference on Combinatorial Optimization and Applications, COCOA 2009 - Huangshan, China Duration: 10 Jun 2009 → 12 Jun 2009

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5573 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	3rd International Conference on Combinatorial Optimization and Applications, COCOA 2009
Country/Territory	China
City	Huangshan
Period	10/06/09 → 12/06/09

Keywords

Approximation algorithm
Minimum weighted connected dominating set
Node-weighted Steiner tree
Polynomial-time approximation scheme

Access to Document

10.1007/978-3-642-02026-1_4

Cite this

Li, X., Xu, X. H., Zou, F., Du, H., Wan, P., Wang, Y., & Wu, W. (2009). A PTAS for node-weighted steiner tree in unit disk graphs. In Combinatorial Optimization and Applications - Third International Conference, COCOA 2009, Proceedings (pp. 36-48). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5573 LNCS). https://doi.org/10.1007/978-3-642-02026-1_4

@inproceedings{d6e6504dd9c54452b9939724ef25530f,

title = "A PTAS for node-weighted steiner tree in unit disk graphs",

abstract = "The node-weighted Steiner tree problem is a variation of classical Steiner minimum tree problem. Given a graph G=(V,E) with node weight function C:V→R+ and a subset X of V, the node-weighted Steiner tree problem is to find a Steiner tree for the set X such that its total weight is minimum. In this paper, we study this problem in unit disk graphs and present a (1+ε)-approximation algorithm for any ε>0, when the given set of vertices is c-local. As an application, we use node-weighted Steiner tree to solve the node-weighted connected dominating set problem in unit disk graphs and obtain a (5+ε)-approximation algorithm.",

keywords = "Approximation algorithm, Minimum weighted connected dominating set, Node-weighted Steiner tree, Polynomial-time approximation scheme",

author = "Xianyue Li and Xu, \{Xiao Hua\} and Feng Zou and Hongwei Du and Pengjun Wan and Yuexuan Wang and Weili Wu",

year = "2009",

doi = "10.1007/978-3-642-02026-1\_4",

language = "英语",

isbn = "3642020259",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "36--48",

booktitle = "Combinatorial Optimization and Applications - Third International Conference, COCOA 2009, Proceedings",

note = "3rd International Conference on Combinatorial Optimization and Applications, COCOA 2009 ; Conference date: 10-06-2009 Through 12-06-2009",

}

Li, X, Xu, XH, Zou, F, Du, H, Wan, P, Wang, Y & Wu, W 2009, A PTAS for node-weighted steiner tree in unit disk graphs. in Combinatorial Optimization and Applications - Third International Conference, COCOA 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5573 LNCS, pp. 36-48, 3rd International Conference on Combinatorial Optimization and Applications, COCOA 2009, Huangshan, China, 10/06/09. https://doi.org/10.1007/978-3-642-02026-1_4

A PTAS for node-weighted steiner tree in unit disk graphs. / Li, Xianyue; Xu, Xiao Hua; Zou, Feng et al.
Combinatorial Optimization and Applications - Third International Conference, COCOA 2009, Proceedings. 2009. p. 36-48 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5573 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A PTAS for node-weighted steiner tree in unit disk graphs

AU - Li, Xianyue

AU - Xu, Xiao Hua

AU - Zou, Feng

AU - Du, Hongwei

AU - Wan, Pengjun

AU - Wang, Yuexuan

AU - Wu, Weili

PY - 2009

Y1 - 2009

N2 - The node-weighted Steiner tree problem is a variation of classical Steiner minimum tree problem. Given a graph G=(V,E) with node weight function C:V→R+ and a subset X of V, the node-weighted Steiner tree problem is to find a Steiner tree for the set X such that its total weight is minimum. In this paper, we study this problem in unit disk graphs and present a (1+ε)-approximation algorithm for any ε>0, when the given set of vertices is c-local. As an application, we use node-weighted Steiner tree to solve the node-weighted connected dominating set problem in unit disk graphs and obtain a (5+ε)-approximation algorithm.

AB - The node-weighted Steiner tree problem is a variation of classical Steiner minimum tree problem. Given a graph G=(V,E) with node weight function C:V→R+ and a subset X of V, the node-weighted Steiner tree problem is to find a Steiner tree for the set X such that its total weight is minimum. In this paper, we study this problem in unit disk graphs and present a (1+ε)-approximation algorithm for any ε>0, when the given set of vertices is c-local. As an application, we use node-weighted Steiner tree to solve the node-weighted connected dominating set problem in unit disk graphs and obtain a (5+ε)-approximation algorithm.

KW - Approximation algorithm

KW - Minimum weighted connected dominating set

KW - Node-weighted Steiner tree

KW - Polynomial-time approximation scheme

UR - https://www.scopus.com/pages/publications/70350626743

U2 - 10.1007/978-3-642-02026-1_4

DO - 10.1007/978-3-642-02026-1_4

M3 - 会议稿件

AN - SCOPUS:70350626743

SN - 3642020259

SN - 9783642020254

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 36

EP - 48

BT - Combinatorial Optimization and Applications - Third International Conference, COCOA 2009, Proceedings

T2 - 3rd International Conference on Combinatorial Optimization and Applications, COCOA 2009

Y2 - 10 June 2009 through 12 June 2009

ER -

Li X, Xu XH, Zou F, Du H, Wan P, Wang Y et al. A PTAS for node-weighted steiner tree in unit disk graphs. In Combinatorial Optimization and Applications - Third International Conference, COCOA 2009, Proceedings. 2009. p. 36-48. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-02026-1_4

A PTAS for node-weighted steiner tree in unit disk graphs

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this