On finding maximum disjoint paths with different colors: computational complexity and practical LP-based algorithms

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

zbMATH Keywords

linear programmingwireless networks\(\mathcal{NP}\)-completenessmaximum disjoint paths with different colors

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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