×

Exact algorithms for finding partial edge-disjoint paths. (English) Zbl 1512.05371

Wang, Lusheng (ed.) et al., Computing and combinatorics. 24th international conference, COCOON 2018, Qing Dao, China, July 2–4, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10976, 14-25 (2018).
Summary: For a given graph \(G\) with non-negative integral edge length, a pair of distinct vertices \(s\) and \(t\), and a given positive integer \(\delta\), the \(k\) Partial Edge-Disjoint Shortest Path (\(k\text{PESP}\))problem aims to compute \(k\) shortest \(st\)-paths among which there are at most \(\delta\) 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+\delta n^{2})\) for (\(k\text{PESP}\)) with \(k=2\). Then observing the algorithm can not be extended for general \(k\), we propose another algorithm with a runtime \(O(\delta 2^{k}n^{k+1})\) in DAGs based on graph transformation. In addition, we show the algorithm can be extended to (\(k\text{PESP}\)) with an extra edge congestion constraint that each edge can be shared by at most \(C\) paths for a given integer \(C\leq k\).
For the entire collection see [Zbl 1390.68029].

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C38 Paths and cycles
05C12 Distance in graphs
PDFBibTeX XMLCite
Full Text: DOI