commit dd42b18a4f79e2c44a9e8c67deb389a8428c5799 parent 1f8e4761803a732802ac4d9c4921a0739e2781a8 Author: Antoine Amarilli <a3nm@a3nm.net> Date: Wed, 14 May 2025 18:37:11 +0200 Merge branch 'master' of a3nm.net:git/wiki_research Diffstat:
| shortest_disjoint_paths | | | 15 | ++++++++++++--- |
1 file changed, 12 insertions(+), 3 deletions(-)
diff --git a/shortest_disjoint_paths b/shortest_disjoint_paths @@ -1,11 +1,20 @@ # Shortest disjoint paths -- reference [berczi2017directed] +[disjoint_paths] where each path is [shortest_path] + +- reference [eilamtzoreff1998disjoint] on two disjoint [shortest_paths] + - generalization in [lochet2021polynomial] to arbitrary constant numbers of [shortest_paths] on [undirected_graphs] +- reference [berczi2017directed] with graph weights - if edge weights can be zero - [np_complete] because can reduce from [disjoint_paths] - if edge weights are positive - 2-disjoint shortest path is [ptime] on [graph_directed] - - other results on [planar_graph] -- open whether 3-disjoint shortest path is ptime on [graph_directed] + - other results on [planar_graphs] +- [open_question]: whether 3-disjoint [shortest_path] is ptime on [graph_directed] +- special case k=2: [shortest_two_disjoint_paths] + +mentioned in [cstheory] question: https://cstheory.stackexchange.com/questions/21987/for-which-values-of-k-is-minimum-length-undirected-k-disjoint-paths-in-mat Up: [disjoint_paths] + +See also: [Shortest_total_disjoint_paths]