Maximum disjoint paths on edge-colored graphs: approximability and tractability

DOI10.3390/a6010001zbMath1461.68144OpenAlexW2142971798MaRDI QIDQ1736537

Yuri Pirola, Paola Bonizzoni, Riccardo Dondi

Publication date: 26 March 2019

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3390/a6010001

zbMATH Keywords

social networkshardness of approximationfixed-parameter algorithmsdisjoint paths

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

Finding disjoint paths on edge-colored graphs: more tractability results, Editorial: Special issue on graph algorithms, 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, Finding colorful paths in temporal graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Variants of constrained longest common subsequence
• On the maximum disjoint paths problem on edge-colored graphs
• Complexity issues in vertex-colored graph pattern matching
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Upper and lower bounds for finding connected motifs in vertex-colored graphs
• Algorithm engineering for color-coding with applications to signaling pathway detection
• Faster fixed-parameter tractable algorithms for matching and packing problems
• A faster parameterized algorithm for set packing
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Balanced Hashing, Color Coding and Approximate Counting
• Color-coding