zbMATH — the first resource for mathematics

New races in parameterized algorithmics. (English) Zbl 1365.68286
Rovan, Branislav (ed.) et al., Mathematical foundations of computer science 2012. 37th international symposium, MFCS 2012, Bratislava, Slovakia, August 27–31, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-32588-5/pbk). Lecture Notes in Computer Science 7464, 19-30 (2012).
Summary: Once having classified an NP-hard problem fixed-parameter tractable with respect to a certain parameter, the race for the most efficient fixed-parameter algorithm starts. Herein, the attention usually focuses on improving the running time factor exponential in the considered parameter, and, in case of kernelization algorithms, to improve the bound on the kernel size. Both from a practical as well as a theoretical point of view, however, there are further aspects of efficiency that deserve attention. We discuss several of these aspects and particularly focus on the search for “stronger parameterizations” in developing fixed-parameter algorithms.
For the entire collection see [Zbl 1246.68054].

68Q25 Analysis of algorithms and problem complexity
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI