Node-weighted Steiner tree approximation in unit disk graphs |
| |
Authors: | Feng Zou Xianyue Li Suogang Gao Weili Wu |
| |
Institution: | (1) Department of Computer Science and Information Engineering, National Cheng Kung University, No 1. University Road, Tainan, 701, Taiwan |
| |
Abstract: | Given a graph G=(V,E) with node weight w:V→R
+ and a subset S⊆V, find a minimum total weight tree interconnecting all nodes in S. This is the node-weighted Steiner tree problem which will be studied in this paper. In general, this problem is NP-hard
and cannot be approximated by a polynomial time algorithm with performance ratio aln n for any 0<a<1 unless NP⊆DTIME(n
O(log n)), where n is the number of nodes in s. In this paper, we are the first to show that even though for unit disk graphs, the problem is still NP-hard and it has a
polynomial time constant approximation. We present a 2.5ρ-approximation where ρ is the best known performance ratio for polynomial time approximation of classical Steiner minimum tree problem in graphs.
As a corollary, we obtain that there is a polynomial time (9.875+ε)-approximation algorithm for minimum weight connected dominating set in unit disk graphs, and also there is a polynomial
time (4.875+ε)-approximation algorithm for minimum weight connected vertex cover in unit disk graphs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|