Finding disjoint paths on edge-colored graphs: more tractability results

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

zbMATH Keywords

approximationsocial networksparameterized complexityedge-colored graphs

Mathematics Subject Classification ID

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