Finding disjoint paths on edge-colored graphs: more tractability results
From MaRDI portal
Publication:1631683
DOI10.1007/s10878-017-0238-6zbMath1412.90157arXiv1609.04951OpenAlexW2963792426MaRDI QIDQ1631683
Florian Sikora, Riccardo Dondi
Publication date: 6 December 2018
Published in: Journal of Combinatorial Optimization, Combinatorial Optimization and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1609.04951
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Finding disjoint paths on edge-colored graphs: more tractability results ⋮ On finding maximum disjoint paths with different colors: computational complexity and practical LP-based algorithms ⋮ Finding colorful paths in temporal graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- On the maximum disjoint paths problem on edge-colored graphs
- Paths of bounded length and their cuts: parameterized complexity and algorithms
- Multicolour paths in graphs: NP-hardness, algorithms, and applications on routing in WDM networks
- Some APX-completeness results for cubic graphs
- Finding disjoint paths on edge-colored graphs: more tractability results
- Maximum disjoint paths on edge-colored graphs: approximability and tractability
- Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
- Completely inapproximable monotone and antimonotone parameterized problems
- New Races in Parameterized Algorithmics
- On Parameterized Approximability
- Color-coding
- Parameterized Algorithms
This page was built for publication: Finding disjoint paths on edge-colored graphs: more tractability results