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 (2007). Quadratic kernelization for convex recoloring of trees. In: G. Lin, Computing and Combinatorics (COCOON 2007). 13th Annual International Conference on Computing and Combinatorics (COCOON 2007), Banff, Alberta, Canada, (86-96). 16-19 July 2007. doi:10.1007/978-3-540-73545-8_11

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads

Author Bodlaender, Hans L.
Fellows, Michael R.
Langston, Michael A.
Ragan, Mark A.
Rosamond, Frances A.
Weyer, Mark
Title of paper Quadratic kernelization for convex recoloring of trees
Conference name 13th Annual International Conference on Computing and Combinatorics (COCOON 2007)
Conference location Banff, Alberta, Canada
Conference dates 16-19 July 2007
Proceedings title Computing and Combinatorics (COCOON 2007)   Check publisher's open access policy
Journal name Lecture Notes in Computer Science   Check publisher's open access policy
Place of Publication Berlin, Germany
Publisher Springer
Publication Year 2007
Sub-type Fully published paper
DOI 10.1007/978-3-540-73545-8_11
ISBN 9783540735441
ISSN 0302-9743
Editor G. Lin
Volume 4598
Start page 86
End page 96
Total pages 11
Language eng
Formatted Abstract/Summary
The Convex Recoloring (CR) problem measures how far a tree of characters differs from exhibiting a so-called “perfect phylogeny”. For 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 connected subtree. The problem was introduced by Moran and Snir, who showed that CR is NP-hard, and described a search-tree based FPT algorithm with a running time of O(k(k/logk) k n 4). The Moran and Snir result did not provide any nontrivial kernelization. Subsequently, a kernelization with a large polynomial bound was established. Here we give the strongest FPT results to date on this problem: (1) We show that in polynomial time, a problem kernel of size O(k 2) can be obtained, and (2) We prove that the problem can be solved in linear time for fixed k. The technique used to establish the second result appears to be of general interest and applicability for bounded treewidth problems.
Subjects 080201 Analysis of Algorithms and Complexity
Keyword Convex recoloring (CR)
Vertex-colored tree T
Q-Index Code E1
Q-Index Status Provisional Code
Institutional Status Non-UQ
Additional Notes Proceedings published in 'Lecture Notes in Computer Science' Book series.

Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 8 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 0 times in Scopus Article
Google Scholar Search Google Scholar
Created: Wed, 11 Mar 2009, 15:20:25 EST by Joanne Mellor on behalf of School of Information Technol and Elec Engineering