B. Yang, S.Q. Zheng, and E. Lu (USA)
network, graph, reliability, shortest path, disjoint paths, NP-complete, approximation
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
