Quadratic kernelization for convex recoloring of trees

Bodlaender, Hans L., Fellows, Michael R., Langston, Michael A., Ragan, Mark A., Rosamond, Frances A. and Weyer, Mark (2011) Quadratic kernelization for convex recoloring of trees. Algorithmica, 61 2: 362-388. doi:10.1007/s00453-010-9404-2

Author Bodlaender, Hans L.
Fellows, Michael R.
Langston, Michael A.
Ragan, Mark A.
Rosamond, Frances A.
Weyer, Mark
Title Quadratic kernelization for convex recoloring of trees
Journal name Algorithmica   Check publisher's open access policy
ISSN 0178-4617
Publication date 2011-10
Year available 2010
Sub-type Article (original research)
DOI 10.1007/s00453-010-9404-2
Volume 61
Issue 2
Start page 362
End page 388
Total pages 27
Place of publication New York, NY, U.S.A.
Publisher Springer
Collection year 2011
Language eng
Formatted abstract
The Convex Recoloring (CR) problem measures how far a tree of characters differs from exhibiting a so-called “perfect phylogeny”. For an input consisting of a vertex-colored tree T, the problem is to determine whether recoloring at most k vertices can achieve a convex coloring, meaning by this a coloring where each color class induces a subtree. The problem was introduced by Moran and Snir (J. Comput. Syst. Sci. 73:1078–1089, 2007; J. Comput. Syst. Sci. 74:850–869, 2008) who showed that CR is NP-hard, and described a search-tree based FPT algorithm with a running time of O(k(k/log k)kn4). The Moran and Snir result did not provide any nontrivial kernelization. In this paper, we show that CR has a kernel of size O(k2).
Keyword Algorithms
Combinatorial algorithms
Fixed parameter tractability
Convex recoloring
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ
Additional Notes Published online 27 March, 2010.

Document type: Journal Article
Sub-type: Article (original research)
Collections: Official 2011 Collection
Institute for Molecular Bioscience - Publications
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 2 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 4 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Mon, 07 Feb 2011, 12:15:42 EST by Susan Allen on behalf of Institute for Molecular Bioscience