> Friedrich-Schiller-Universität Jena
Fakultät für Mathematik und Informatik
Theoretische Informatik I
> Research/Project AREG

DFG Project AREG: Algorithms for Generating Quasi-Regular Structures in Graphs

Project AREG (DFG Project NI 369/9-1) started in February 2008.

Project Description

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

People

Photo of René van Bevern René van Bevern
Dipl.-Inf., Researcher
Room 3323
Phone: (+49) 3641 9 46324

Head: Rolf Niedermeier and Jiong Guo
Valid HTML 4.01! Last modified: Tue May 2 11:27:46 CEST 2010