@inproceedings{af41719ad4d84f5fbad920ca54ce4d39,
title = "Greedy localization, iterative compression, and modeled crown reductions: new fpt techniques, an improved algorithm for set splitting, and a novel 2k kernelization for vertex cover",
abstract = "The two objectives of this paper are: (1) to articulate three new general techniques for designing FPT algorithms, and (2) to apply these to obtain new FPT algorithms for SET SPLITTING and VERTEX COVER. In the case of SET SPLITTING, we improve the best previous O*(72k) FPT algorithm due to Dehne, Fellows and Rosamond [DFR03], to O*(8k) by an approach based on greedy localization in conjunction with modeled crown reduction. In the case of VERTEX COVER, we describe a new approach to 2k kernelization based on iterative compression and crown reduction, providing a potentially useful alternative to the Nemhauser-Trotter 2k kernelization. {\textcopyright} Springer-Verlag 2004.",
keywords = "Algorithms, FPT algorithms, Kernelization, New approaches, Set splitting, Vertex cover, Iterative methods",
author = "F Dehne and M. Fellows and F. Rosamond and P. Shaw",
year = "2004",
doi = "10.1007/978-3-540-28639-4_24",
language = "English",
isbn = "978-3-540-23071-7",
series = "Lecture Notes in Computer Science ",
publisher = "Springer",
pages = "271--280",
editor = "Rod Downey and Michael Fellows and Frank Dehne",
booktitle = "Parameterized and Exact Computation",
address = "Switzerland",
}