caa a22 4500 445805536 CHVBK 20180317145155.0 cr unu---uuuuu 170323e20111001xx s 000 0 eng 10.1007/s00453-010-9404-2 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9404-2 Quadratic Kernelization for Convex Recoloring of Trees [Elektronische Daten] [Hans Bodlaender, Michael Fellows, Michael Langston, Mark Ragan, Frances Rosamond, Mark Weyer] 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)k n 4). The Moran and Snir result did not provide any nontrivial kernelization. In this paper, we show that CR has a kernel of size O(k 2). The Author(s), 2010 Algorithms nationallicence Combinatorial algorithms nationallicence Fixed parameter tractability nationallicence Kernelization nationallicence Convex recoloring nationallicence Trees nationallicence Phylogeny nationallicence Bodlaender Hans Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands aut Fellows Michael Parameterized Complexity Research Unit, Office of the DVC (Research), University of Newcastle, NSW 2308, Callaghan, Australia aut Langston Michael Australian Research Council Centre of Excellence in Bioinformatics, Brisbane, Australia aut Ragan Mark Australian Research Council Centre of Excellence in Bioinformatics, Brisbane, Australia aut Rosamond Frances Parameterized Complexity Research Unit, Office of the DVC (Research), University of Newcastle, NSW 2308, Callaghan, Australia aut Weyer Mark Institut für Informatik, Humboldt-Universität zu Berlin, Berlin, Germany aut Algorithmica Springer-Verlag 61/2(2011-10-01), 362-388 0178-4617 61:2<362 2011 61 453 https://doi.org/10.1007/s00453-010-9404-2 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9404-2 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Bodlaender Hans Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands aut NATIONALLICENCE 700 1- Fellows Michael Parameterized Complexity Research Unit, Office of the DVC (Research), University of Newcastle, NSW 2308, Callaghan, Australia aut NATIONALLICENCE 700 1- Langston Michael Australian Research Council Centre of Excellence in Bioinformatics, Brisbane, Australia aut NATIONALLICENCE 700 1- Ragan Mark Australian Research Council Centre of Excellence in Bioinformatics, Brisbane, Australia aut NATIONALLICENCE 700 1- Rosamond Frances Parameterized Complexity Research Unit, Office of the DVC (Research), University of Newcastle, NSW 2308, Callaghan, Australia aut NATIONALLICENCE 700 1- Weyer Mark Institut für Informatik, Humboldt-Universität zu Berlin, Berlin, Germany aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/2(2011-10-01), 362-388 0178-4617 61:2<362 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer