Algorithmen zur Erzeugung quasiregulärer Strukturen in Graphen (AREG)

• Applicant: Professor Dr. Rolf Niedermeier (†)
• Subject Area: Theoretical Computer Science
• Term: from 2008 to 2012
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 66926305

Ziel des Projekts AREG ist die Entwicklung effizienter Algorithmen zur Detektion quasiregulärer Strukturen in Graphen. Dies schließt als Spezialfälle insbesondere wichtige Überdeckungsprobleme wie Vertex Cover mit ein. Die meisten in diesem Kontext auftretenden Probleme sind NP-schwer. Viele der betrachteten Probleme fallen unter den Oberbegriff der Graphmodifikation, wo durch möglichst wenige Modifikationen (Kanten und Knoten betreffend) in einem gegebenen Graph eine gewünschte Struktur erzeugt werden soll. Die Jenaer Arbeitsgruppe hat sich über die letzten Jahre ein breites Methodenrepertoire (Datenreduktion, iterative Kompression, Suchbäume etc.) zur (exakten) algorithmischen Handhabung von Quasiregularitäts- bzw. Graphmodifikationsproblemen erarbeitet, das weiterentwickelt und gewinnbringend eingesetzt werden soll. Gegenüber der ersten Projektphase soll auf Basis der inzwischen erzielten, vorwiegend theoretischen Ergebnisse noch stärker der Algorithm Engineering-Aspekt verfolgt werden.

• DFG Programme: Research Grants
• Participating Person: Professor Dr. Jiong Guo