Exact Algorithms for Finding Partial Edge-Disjoint Paths

摘要

For a given graph G with non-negative integral edge length, a pair of distinct vertices s and t, and a given positive integer δ, the k partial edge-disjoint shortest path (kPESP) problem aims to compute k shortest si-paths among which there are at most δ edges shared by at least two paths. In this paper, we first present an exact algorithm with a runtime O(mn log_(1+m) n + δn~2) for kPESP with k = 2. Then observing the algorithm can not be extended for general k, we propose another algorithm with a runtime O(δ2~kn~(k+1)) in DAGs based on graph transformation. In addition, we show the algorithm can be extended to kPESP with an extra edge congestion constraint that each edge can be shared by at most C paths for a given integer C ≤ k.