Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs
verfasst von : Feng Zou, Xianyue Li, Donghyun Kim, 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
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
a
ln
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 show that for unit disk graph, the problem is still NP-hard, however it has polynomial time constant approximation. We will present a 4-approximation and 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 polynomial time (9.875+
ε
)-approximation algorithm for minimum weight connected dominating set in unit disk graphs.