2005 | OriginalPaper | Chapter
Finding Two Disjoint Paths in a Network with Normalized α + -MIN-SUM Objective Function
Authors : Bing Yang, S. Q. Zheng, Enyue Lu
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.