Finding Two Disjoint Paths in a Network with Normalized α-MIN-SUM Objective Function

B. Yang, S.Q. Zheng, and E. Lu (USA)

Keywords

network, graph, reliability, shortest path, disjoint paths, NPcomplete, approximation

Abstract

Given a number ¥ with ¦¨§©¥§ , a graph !#"%$ and two nodes & and ' in  , we consider the problem of finding two disjoint paths (0) and (21 from & to ' such that 3547698@'BACD(E)F$HG¥PIQ3D47698@'BACD(!1R$ with 3D47698@'BACD(E)F$TS 354R698U'BAV5(%W@$ is minimized. The paths may be node-disjoint or edge-disjoint, and the network may be directed or undi rected. This problem has applications in reliable com munication. We show that all four versions of this prob lem are NP-complete. Then we give an approximation of 1)YXa` , and show that this bound is best possible for directed graphs. For acyclic directed graphs, we also give a pseudo polynomial-time algorithm for finding optimal solutions.

Important Links:



Go Back