On the maximum disjoint paths problem on edge-colored graphs

DOI10.1016/j.disopt.2012.01.002zbMath1242.90281OpenAlexW3104897947MaRDI QIDQ435732

Bang Ye Wu

Publication date: 12 July 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2012.01.002

zbMATH Keywords

algorithmapproximation algorithmconnectivitydisjoint pathssocial network analysiscolored-graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59) Coloring of graphs and hypergraphs (05C15)

Related Items (5)

Finding disjoint paths on edge-colored graphs: more tractability results ⋮ On the edge capacitated Steiner tree problem ⋮ Maximum disjoint paths on edge-colored graphs: approximability and tractability ⋮ On finding maximum disjoint paths with different colors: computational complexity and practical LP-based algorithms ⋮ Multicolour paths in graphs: NP-hardness, algorithms, and applications on routing in WDM networks

Cites Work

• Unnamed Item
• Unnamed Item
• A simplified NP-complete satisfiability problem
• On the complexity of vertex-disjoint length-restricted path problems
• Graph minors. XIII: The disjoint paths problem
• Approximation algorithms and hardness results for labeled connectivity problems
• Solving the 2-disjoint paths problem in nearly linear time
• Length-bounded cuts and flows
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• Properly Coloured Cycles and Paths: Results and Open Problems
• Combinatorial Gray Codes
• The complexity of finding maximum disjoint paths with length constraints

This page was built for publication: On the maximum disjoint paths problem on edge-colored graphs