Reflections on multivariate algorithmics and problem parameterization. (English) Zbl 1230.68096

Niedermeier, Rolf

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].

MSC:

68Q17	Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W40	Analysis of algorithms

Keywords:

multivariate algorithmics; problem parameterization