DFG Project AREG: Algorithms for Generating Quasi-Regular Structures in Graphs
Project AREG (DFG Project NI 369/9-1) started in February 2008.
Algorithms to find quasi-regular structures in graphs make
up a broad field in graph algorithmics. A simple special
case is the well-known Vertex Cover problem. Recently, new
problems in this context with interesting applications were
introduced, and new techniques were developed. Examples
of such techniques are, e.g, the interative compression
technique or the characterization via forbidden subgraphs.
However, the studies of the problems and the techniques were
quite specific and isolated from each other up to now. In
this project, these problems and techniques are studied
in a more general context, using all relevant algorithmic
methods for NP-hard problems (including experiments).
Head: Rolf Niedermeier and Jiong Guo