@inproceedings{c83da330824044948f6dd12bc1522385,

title = "Fast FPT-algorithms for cleaning grids",

abstract = "We consider the problem that, given a graph G and a parameter k, asks whether the edit distance of G and a rectangular grid is at most k. We examine the general case where the edit operations are vertex/edge removals and additions. If the dimensions of the grid are given in advance, we give a parameterized algorithm that runs in 2O(log k·k) + O(n 3) steps. In the case where the dimensions of the grid are not given we give a parameterized algorithm that runs in 2O(log k·k) + O(k2·n3) steps. We insist on parameterized algorithms with running times where the relation between the polynomial and the non-polynomial part is additive. Our algorithm is based on the technique of kernelization. In particular we prove that for each version of the above problem there exists a kernel of size O(k4).",

author = "Josep D{\'i}az and Thilikos, {Dimitrios M.}",

year = "2006",

doi = "10.1007/11672142_29",

language = "English (US)",

isbn = "3540323015",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "361--371",

booktitle = "STACS 2006",

note = "STACS 2006: 23rd Annual Symposium on Theoretical Aspects of Computer Science, Proceedings ; Conference date: 23-02-2006 Through 25-02-2006",

}