On finding maximum disjoint paths with different colors: computational complexity and practical LP-based algorithms
From MaRDI portal
Publication:2232599
DOI10.1016/j.tcs.2021.08.009OpenAlexW3195653587MaRDI QIDQ2232599
Longkun Guo, Yunyun Deng, Yi Chen, Kewen Liao
Publication date: 6 October 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2021.08.009
linear programmingwireless networks\(\mathcal{NP}\)-completenessmaximum disjoint paths with different colors
Cites Work
- On the maximum disjoint paths problem on edge-colored graphs
- Edge-disjoint paths in planar graphs
- The directed subgraph homeomorphism problem
- Finding disjoint paths on edge-colored graphs: more tractability results
- Maximum disjoint paths on edge-colored graphs: approximability and tractability
- Exact algorithms for finding partial edge-disjoint paths
- On fault-tolerant path optimization under QoS constraint in multi-channel wireless networks
- Solving the 2-disjoint paths problem in nearly linear time
- The all-or-nothing multicommodity flow problem
- Multicommodity flow, well-linked terminals, and routing problems
- A Polynomial Solution to the Undirected Two Paths Problem
- Finding k Disjoint Paths in a Directed Planar Graph
- All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs
This page was built for publication: On finding maximum disjoint paths with different colors: computational complexity and practical LP-based algorithms