2015 | OriginalPaper | Buchkapitel
PTAS’s for Some Metric p-source Communication Spanning Tree Problems
Autoren: Santiago V. Ravelo, Carlos E. Ferreira
Verlag: Springer International Publishing
In this work we consider some NP-hard cases of the metric
p
-source communication spanning tree problem (metric
p
-
OCT
). Given an undirected complete graph
G
= (
V
,
E
) with non-negative length
ω
(
e
) associated to each edge
e
∈
E
satisfying the triangular inequality, a set
S
⊆
V
of
p
vertices and non-negative routing requirements
ψ
(
u
,
v
) between all pairs of nodes
u
∈
S
and
v
∈
V
, the metric
p
-
OCT
’s objective is to find a spanning tree
T
of
G
, that minimizes: ∑
u
∈
S
∑
v
∈
V
ψ
(
u
,
v
)
d
(
T
,
u
,
v
), where
d
(
H
,
x
,
y
) is the minimum distance between nodes
x
and
y
in a graph
H
⊆
G
. This problem is a particular case of the optimum communication spanning tree problem (
OCT
). We prove a general result which allows us to derive polynomial approximation schemes for some NP-hard cases of the metric
p
-
OCT
improving the existing ratios for these problems.