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

DOI10.3390/a6010001zbMath1461.68144MaRDI 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 networks; hardness of approximation; fixed-parameter algorithms; disjoint paths

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C38: Paths and cycles

05C15: Coloring of graphs and hypergraphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68Q27: Parameterized complexity, tractability and kernelization

Related Items

Multicolour paths in graphs: NP-hardness, algorithms, and applications on routing in WDM networks, Finding disjoint paths on edge-colored graphs: more tractability results, Editorial: Special issue on graph algorithms, Finding colorful paths in temporal graphs, On finding maximum disjoint paths with different colors: computational complexity and practical LP-based algorithms

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