Academic
Publications
A PTAS for Node-Weighted Steiner Tree in Unit Disk Graphs

A PTAS for Node-Weighted Steiner Tree in Unit Disk Graphs,10.1007/978-3-642-02026-1_4,Xianyue Li,Xiao-hua Xu,Feng Zou,Hongwei Du,Peng-jun Wan,Yuexuan

A PTAS for Node-Weighted Steiner Tree in Unit Disk Graphs   (Citations: 1)
BibTex | RIS | RefWorks Download
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.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: