Quadratic Kernelization for Convex Recoloring of Trees

DOI10.1007/978-3-540-73545-8_11MaRDI QIDQ3608834zbMATH OpenOpenAlexFDO

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

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

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)

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

Cited in

(11)

• 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 kernel for convex recoloring of weighted forests
• A \(2^{O(k)}\)poly\((n)\) algorithm for the parameterized convex recoloring problem
• The balanced connected subgraph problem for geometric intersection graphs
• On the complexity of some colorful problems parameterized by treewidth
• Approximation and Online Algorithms
• 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)