Failure disjoint paths
Given a weighted directed graph where some arcs can fail while others are reliable, we aim to compute a shortest pair of failure-disjoint paths. If a reliable arc is used by both paths, its cost is counted only once. We present a polynomial time algorithm to solve the problem.
- Electrical Engineering, Electronic Engineering, Information Engineering
- polynomial time algorithms
- shortest paths
- disjoint paths
International Symposium on Combinatorial Optimization