Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
A PTAS for Node-Weighted Steiner Tree in Unit Disk Graphs
verfasst von : Xianyue Li, Xiao-Hua Xu, Feng Zou, Hongwei Du, Pengjun Wan, Yuexuan Wang, Weili Wu
Erschienen in: Combinatorial Optimization and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.