The directed 2-linkage problem with length constraints

Theoretical Computer Science - Tập 814 - Trang 69-73 - 2020
J. Bang-Jensen1, T. Bellitto1, W. Lochet2, A. Yeo1
1Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark
2University of Bergen, Norway

Tài liệu tham khảo

2018 Bang-Jensen, 2009 Bérczi, 2017, The directed disjoint shortest paths problem, 13:1 Björklund, 2014, Shortest two disjoint paths in polynomial time, 211 Cygan, 2015 Colin de Verdière, 2011, Shortest vertex-disjoint two-face paths in planar graphs, ACM Trans. Algorithms, 7, 19:1 Eilam-Tzoreff, 1998, The disjoint shortest paths problem, Discrete Appl. Math., 85, 113, 10.1016/S0166-218X(97)00121-2 Fortune, 1980, The directed subgraph homeomorphism problem, Theor. Comput. Sci., 10, 111, 10.1016/0304-3975(80)90009-2 Gottschau, 2019, The undirected two disjoint shortest paths problem, Oper. Res. Lett., 47, 70, 10.1016/j.orl.2018.11.011 Kawarabayashi, 2012, The disjoint paths problem in quadratic time, J. Comb. Theory, Ser. B, 102, 424, 10.1016/j.jctb.2011.07.004 Kobayashi, 2019, Two disjoint shortest paths problem with non-negative edge length, Oper. Res. Lett., 47, 66, 10.1016/j.orl.2018.11.012 Kobayashi, 2010, On shortest disjoint paths in planar graphs, Discrete Optim., 7, 234, 10.1016/j.disopt.2010.05.002 Robertson, 1995, Graph minors. XIII: the disjoint paths problem, J. Comb. Theory, Ser. B, 63, 65, 10.1006/jctb.1995.1006 Slivkins, 2010, Parameterized tractability of edge-disjoint paths on directed acyclic graphs, SIAM J. Discrete Math., 24, 146, 10.1137/070697781