Maximum disjoint paths on edge-colored graphs: approximability and tractability
From MaRDI portal
Publication:1736537
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
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