×

Two disjoint shortest paths problem with non-negative edge length. (English) Zbl 1476.05188

Summary: In the two disjoint shortest paths problem ( 2-DSPP), the input is a graph (or a digraph) and its vertex pairs \((s_1, t_1)\) and \((s_2, t_2)\), and the objective is to find two vertex-disjoint paths \(P_1\) and \(P_2\) such that \(P_i\) is a shortest path from \(s_i\) to \(t_i\) for \(i = 1, 2\), if they exist. In this paper, we give a first polynomial-time algorithm for the undirected version of the 2-DSPP with an arbitrary non-negative edge length function.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C38 Paths and cycles
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Bérczi, Kristóf; Kobayashi, Yusuke, The directed disjoint shortest paths problem, (Proceedings of the 25th Annual European Symposium on Algorithms (ESA 2017) (2017), Kristóf Bérczi Yusuke Kobayashi), 13:1-13:13 · Zbl 1241.05061
[2] Eilam-Tzoreff, Tali, The disjoint shortest paths problem, Discrete Appl. Math., 85, 2, 113-138 (1998) · Zbl 0902.68147
[3] Fortune, Steven; Hopcroft, John E.; Wyllie, James, The directed subgraph homeomorphism problem, Theoret. Comput. Sci., 10, 111-121 (1980) · Zbl 0419.05028
[4] Marinus Gottschau, Marcus Kaiser, Clara Waldmann, The undirected two disjoint shortest paths problem. arXiv:1809.03820; Marinus Gottschau, Marcus Kaiser, Clara Waldmann, The undirected two disjoint shortest paths problem. arXiv:1809.03820
[5] Karp, Richard M., On the computational complexity of combinatorial problems, Networks, 5, 45-68 (1975) · Zbl 0324.05003
[6] Lynch, James F., The equivalence of theorem proving and the interconnection problem, SIGDA Newsl., 5, 3, 31-36 (1975)
[7] Robertson, Neil; Seymour, Paul D., Graph minors. XIII. The disjoint paths problem, J. Combin. Theory Ser. B, 63, 1, 65-110 (1995) · Zbl 0823.05038
[8] Seymour, Paul D., Disjoint paths in graphs, Discrete Math., 29, 293-309 (1980) · Zbl 0457.05043
[9] Shiloach, Yossi, A polynomial solution to the undirected two paths problem, J. ACM, 27, 3, 445-456 (1980) · Zbl 0475.68042
[10] Thomassen, Carsten, 2-linked graphs, European J. Combin., 1, 371-378 (1980) · Zbl 0457.05044
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.