wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

shortest_disjoint_paths (375B)

      1 # Shortest disjoint paths
      2 
      3 - reference [berczi2017directed]
      4   - if edge weights can be zero
      5     - [np_complete] because can reduce from [disjoint_paths]
      6   - if edge weights are positive
      7     - 2-disjoint shortest path is [ptime] on [graph_directed]
      8   - other results on [planar_graph]
      9 - open whether 3-disjoint shortest path is ptime on [graph_directed]
     10 
     11 Up: [disjoint_paths]