zbMATH — the first resource for mathematics

Reflections on multivariate algorithmics and problem parameterization. (English) Zbl 1230.68096
Marion, Jean-Yves (ed.) et al., STACS 2010. 27th international symposium on theoretical aspects of computer science, Nancy, France, March 4–6, 2010. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-16-3). LIPIcs – Leibniz International Proceedings in Informatics 5, 17-32, electronic only (2010).
Summary: Research on parameterized algorithmics for NP-hard problems has steadily grown over the last years. We survey and discuss how parameterized complexity analysis naturally develops into the field of multivariate algorithmics. Correspondingly, we describe how to perform a systematic investigation and exploitation of the “parameter space” of computationally hard problems.
For the entire collection see [Zbl 1213.68051].

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W40 Analysis of algorithms
Full Text: DOI Link