B. Yang, S.Q. Zheng, and S. Katukam (USA)
network, routing, reliability, graph, shortest path, disjoint paths,algorithm, complexity.
Given a network and two nodes and in , we consider the problem of finding two disjoint paths from to such that the length of the shorter path 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 show that all four versions of this problem are NP-complete and polynomial-time approximation algorithms for obtaining solutions with bounded error are impossible unless P = NP. We also show that all four versions of this problem are NP-complete and polynomial-time approximation algorithms for obtaining solutions with bounded error are impossible unless P = NP even when all edges have the same length. For a special case of this problem, we give a polynomial-time algorithm for finding optimal solutions.
Important Links:
Go Back
