@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",
}