Quadratic kernelization for convex recoloring of trees

DOI10.1007/s00453-010-9404-2zbMath1234.68146OpenAlexW2404791952WikidataQ57198691 ScholiaQ57198691MaRDI QIDQ639283

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

Publication date: 20 September 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-010-9404-2

zbMATH Keywords

fixed parameter tractabilitytreesphylogenycombinatorial algorithmskernelizationconvex recoloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) 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

1.5-approximation algorithm for the 2-convex recoloring problem ⋮ Strong intractability results for generalized convex recoloring problems ⋮ Parameterized complexity of happy coloring problems ⋮ Hardness and inapproximability of convex recoloring problems ⋮ Exact exponential algorithms to find tropical connected sets of minimum size ⋮ The convex recoloring problem: polyhedra, facets and computational experiments

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Experiments on data reduction for optimal domination in networks
• Improved approximation algorithm for convex recoloring of trees
• Convex recolorings of strings and trees: Definitions, hardness results and algorithms
• On problems without polynomial kernels
• Inapproximability and approximability of maximal tree routing and coloring
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Efficient approximation of convex recolorings
• The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
• Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Polynomial-time data reduction for dominating set
• The Complexity of Minimum Convex Coloring
• Quadratic Kernelization for Convex Recoloring of Trees
• Incompressibility through Colors and IDs
• Vertex packings: Structural properties and algorithms