shortest_disjoint_paths (906B)
1 # Shortest disjoint paths 2 3 [disjoint_paths] where each path is [shortest_path] 4 5 - reference [eilamtzoreff1998disjoint] on two disjoint [shortest_paths] 6 - generalization in [lochet2021polynomial] to arbitrary constant numbers of [shortest_paths] on [undirected_graphs] 7 - reference [berczi2017directed] with graph weights 8 - if edge weights can be zero 9 - [np_complete] because can reduce from [disjoint_paths] 10 - if edge weights are positive 11 - 2-disjoint shortest path is [ptime] on [graph_directed] 12 - other results on [planar_graphs] 13 - [open_question]: whether 3-disjoint [shortest_path] is ptime on [graph_directed] 14 - special case k=2: [shortest_two_disjoint_paths] 15 16 mentioned in [cstheory] question: https://cstheory.stackexchange.com/questions/21987/for-which-values-of-k-is-minimum-length-undirected-k-disjoint-paths-in-mat 17 18 Up: [disjoint_paths] 19 20 See also: [Shortest_total_disjoint_paths]