Parameterized complexity of the MinCCA problem on graphs of bounded decomposability

DOI10.1016/j.tcs.2017.06.013zbMath1372.68126arXiv1605.00532MaRDI QIDQ2399617

Christophe Paul, Didem Gözüpek, Mordechai Shalom, Ignasi Sau, 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

zbMATH Keywords

dynamic programming; treewidth; planar graph; parameterized complexity; FPT algorithm; minimum changeover cost arborescence; tree-cutwidth; \(\mathsf{FPT}\) algorithm

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C15: Coloring of graphs and hypergraphs

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

05C85: Graph algorithms (graph-theoretic aspects)