Quadratic Kernelization for Convex Recoloring of Trees

DOI10.1007/978-3-540-73545-8_11zbMATH Open1206.68141OpenAlexW2561728979MaRDI QIDQ3608834FDOQ3608834

Mark A. Ragan, Michael A. Langston, Frances Rosamond, Michael R. Fellows, Hans L. Bodlaender, Mark Weyer

Publication date: 6 March 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-73545-8_11

Recommendations

• Quadratic kernelization for convex recoloring of trees
• Convex recoloring of paths
• A \(2^{O(k)}\)poly\((n)\) algorithm for the parameterized convex recoloring problem
• A kernel for convex recoloring of weighted forests
• Convex recoloring of paths

zbMATH Keywords

algorithmscomplexity

Mathematics Subject Classification ID

Problems related to evolution (92D15) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Cited In (10)

• Kernelization: new upper and lower bound techniques
• Convex Recoloring Revisited: Complexity and Exact Algorithms
• Quadratic kernelization for convex recoloring of trees
• Upper and lower bounds for finding connected motifs in vertex-colored graphs
• Constraining Images of Quadratic Arboreal Representations
• A \(2^{O(k)}\)poly\((n)\) algorithm for the parameterized convex recoloring problem
• The balanced connected subgraph problem for geometric intersection graphs
• Approximation and Online Algorithms
• On the complexity of some colorful problems parameterized by treewidth
• Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems

This page was built for publication: Quadratic Kernelization for Convex Recoloring of Trees

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