Parameterized complexity of the MinCCA problem on graphs of bounded decomposability

DOI10.1016/J.TCS.2017.06.013MaRDI QIDQ6828431zbMATH OpenFDO

Authors Didem Gözüpek, Sibel Özkan, Christophe Paul, Ignasi Sau, Mordechai Shalom

Publication date 24 August 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2017.06.013

zbMATH Keywords

FPT algorithmminimum changeover cost arborescenceparameterized complexityplanar graphtree-cutwidthtreewidth

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Cited in

(2)

• A new width parameter of graphs based on edge cuts: -edge-crossing width
• Slim tree-cut width

This page was built for publication: Parameterized complexity of the MinCCA problem on graphs of bounded decomposability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6828431)