Parameterized complexity of the MinCCA problem on graphs of bounded decomposability
DOI10.1016/j.tcs.2017.06.013zbMath1372.68126arXiv1605.00532OpenAlexW2949267493MaRDI QIDQ2399617
Christophe Paul, Mordechai Shalom, Ignasi Sau, Didem Gözüpek, Sibel Özkan
Publication date: 24 August 2017
Published in: Theoretical Computer Science, Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1605.00532
dynamic programmingtreewidthplanar graphparameterized complexityFPT algorithmminimum changeover cost arborescencetree-cutwidth\(\mathsf{FPT}\) algorithm
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (4)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- The structure of graphs not admitting a fixed immersion
- On minimum reload cost cycle cover
- The minimum reload \(s-t\) path, trail and walk problems
- On the parameterized complexity of multiple-interval graph problems
- The complexity of a minimum reload cost diameter problem
- An FPT 2-approximation for tree-cut decomposition
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- On the complexity of constructing minimum changeover cost arborescences
- Parametrized complexity theory.
- Algorithmic Applications of Tree-Cut Width
- On Minimum Changeover Cost Arborescences
- On minimum reload cost paths, tours, and flows
- OPTIMAL BINARY SPACE PARTITIONS FOR SEGMENTS IN THE PLANE
- Parameterized Algorithms
- Reload cost problems: Minimum diameter spanning tree
- Constructing minimum changeover cost arborescenses in bounded treewidth graphs
This page was built for publication: Parameterized complexity of the MinCCA problem on graphs of bounded decomposability
