Quadratic kernelization for convex recoloring of trees
type: Item
instance of: scholarly article
title: Quadratic kernelization for convex recoloring of trees
zbMATH Open document ID: 1234.68146
author: Hans L. Bodlaender
author: Michael R. Fellows
author: Michael A. Langston
author: Mark A. Ragan
author: Mark Weyer
author: Frances Rosamond
published in: Algorithmica
publication date: 2011-09-20T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5948543
zbMATH Keywords: combinatorial algorithms
zbMATH Keywords: fixed parameter tractability
zbMATH Keywords: kernelization
zbMATH Keywords: convex recoloring
zbMATH Keywords: trees
zbMATH Keywords: phylogeny
MaRDI profile type: Publication
full work available at URL: s00453-010-9404-2
OpenAlex ID: W2404791952
Wikidata QID: Q57198691
cites work: Experiments on data reduction for optimal domination in networks
cites work: Polynomial-time data reduction for dominating set
cites work: Improved approximation algorithm for convex recoloring of trees
cites work: On problems without polynomial kernels
cites work: Quadratic Kernelization for Convex Recoloring of Trees
cites work: The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
cites work: Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
cites work: Inapproximability and approximability of maximal tree routing and coloring
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Q4273871
cites work: Incompressibility through Colors and IDs
cites work: Q3549693
cites work: Q3600916
cites work: The Complexity of Minimum Convex Coloring
cites work: Efficient approximation of convex recolorings
cites work: Convex recolorings of strings and trees: Definitions, hardness results and algorithms
cites work: Vertex packings: Structural properties and algorithms
cites work: Q5710169
cites work: Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems
DOI: 10.1007/S00453-010-9404-2
description: scientific article; zbMATH DE number 5948543