Projects

DFG-Project PIAF (NI 369/4): “Fixed-Parameter Algorithms”

In the last few years fixed-parameter algorithms developed into an important alternative to heuristic and approximation algorithms for solving combinatorially hard problems. The main idea of fixed-parameter algorithms is to restrict the seemingly inherent combinatorial explosion of solving algorithms for these problems to problem-specific parameters. The project PIAF aims at an investigation of the research field of fixed-parameter algorithms also taking into regard practical aspects: Implementation and experiments with real-world data shall be an equally important component of the project. With respect to practical applications, we concentrate on central techniques such as data reduction by efficient preprocessing. We investigate fundamental problems as Vertex Cover and Dominating Set (in particular, variants of these problems arising in practice). The relationships of fields such as heuristic or approximation algorithms to fixed-parameter algorithms will also be part of our project.

DFG-Project DARE (GU 1023/1-1): “Data Reduction and Problem Kernels”

DFG-Project PABI (NI 369/7-1): “Parameterized algorithmics for bioinformatics”

DFG-Project AREG (NI 369/9-1): “Algorithms for Generating Quasi-Regular Structures in Graphs”

DAAD-Project D/05/57666 (India–Germany Joint Research Collaboration): “Provably Efficient Exact Algorithms for Computationally Hard Problems”

Previous visits:

• Rolf Niedermeier in Chennai, March 2008
• Venkatesh Raman in Jena, January 2008
• Michael Dom in Chennai, October 2007
• Somnath Sikdar in Jena, August 2006–October 2006 and July 2007–August 2007
• Hannes Moser in Chennai, February 2007
• Saket Saurabh in Jena, July 2007–August 2007