Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Finding Two Disjoint Paths in a Network with Normalized α + -MIN-SUM Objective Function
verfasst von : Bing Yang, S. Q. Zheng, Enyue Lu
Erschienen in: Algorithms and Computation
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 number
α
with 0 <
α
< 1, a network
G
= (
V
,
E
) and two nodes
s
and
t
in
G
, we consider the problem of finding two disjoint paths
P
1
and
P
2
from
s
to
t
such that
length
(
P
1) ≤
length
(
P
2
) and
length
(
P
1
) +
α
·
length
(
P
2
) is minimized. The paths may be node-disjoint or edge-disjoint, and the network may be directed or undirected. This problem has applications in reliable communication. We prove an approximation ratio
${1+\alpha} \over {2\alpha}$
for all four versions of this problem, and also show that this ratio cannot be improved for the two directed versions unless P = NP. We also present Integer Linear Programming formulations for all four versions of this problem. For a special case of this problem, we give a polynomial-time algorithm for finding optimal solutions.