Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
A PTAS for the Metric Case of the Minimum Sum-Requirement Communication Spanning Tree Problem
verfasst von : Santiago V. Ravelo, Carlos E. Ferreira
Erschienen in: Algorithms and Discrete Applied Mathematics
Verlag: Springer International Publishing
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
This work considers the metric case of the minimum sum-requirement communication spanning tree problem (
SROCT
), which is an NP-hard particular case of the minimum communication spanning tree problem (
OCT
). Given an undirected graph
G
= (
V
,
E
) with non-negative lengths
ω
(
e
) associated to the edges satisfying the triangular inequality and non-negative routing weights
r
(
u
) associated to nodes
u
∈
V
, the objective is to find a spanning tree
T
of
G
, that minimizes:
$\frac{1}{2}\sum_{u\in V}\sum_{v\in V}\left(r(u)+r(v)\right)d(T,u,v)$
, where
d
(
H
,
x
,
y
) is the minimum distance between nodes
x
and
y
in a graph
H
⊆
G
. We present a polynomial approximation scheme for the metric case of the
SROCT
improving the until now best existing approximation algorithm for this problem.