Algorithmics and Computational Complexity

Data Reduction in Parameterized Algorithmics - New Models and Methods (DAMM)

Synopsis

Preprocessing by means of data reduction rules is a common approach for the algorithmic treatment of combinatorially difficult and compute-intensive problems. Parameterized Algorithmics formalizes the concept of preprocessing in terms of problem kernels. So far, research mainly focussed on the size of the problem kernel and lacked a broader analysis of preprocessing. Thus, the goal of DAMM is to investigate different aspects of preprocessing taking into consideration other interesting properties of problem kernels, such as the running time for example. We also aim at developing kernelizations with respect to "non-standard" and "multivariate" parameterizations which could be of practical interest. Finally, we will consider different kernelization models that generalize the concept of problem kernels, such as Turing kernels, analyzing their relations and possible applications.

Funded by

Deutsche Forschungsgemeinschaft (Project DAMM, NI 369/13)

Time

December 2012 - 2018

Head: Rolf Niedermeier

People