Deng, Yunyun; Guo, Longkun; Huang, Peihuang 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]. Cited in 1 Document MSC: 05C85 Graph algorithms (graph-theoretic aspects) 05C38 Paths and cycles 05C12 Distance in graphs Keywords:partial edge-disjoint path; exact algorithm; directed acyclic graph; restricted shortest path PDFBibTeX XMLCite \textit{Y. Deng} et al., Lect. Notes Comput. Sci. 10976, 14--25 (2018; Zbl 1512.05371) Full Text: DOI