311568 20240928181615.0 G:(GEPRIS)66926305 G:(GEPRIS)66926305 66926305 GEPRIS http://gepris.its.kfa-juelich.de Algorithmen zur Erzeugung quasiregulärer Strukturen in Graphen (AREG) 2008 - 2012 Professor Dr. Rolf Niedermeier DFG project G:(GEPRIS)66926305 d 2008 - 2012 Deutsche Forschungsgemeinschaft I:(DE-588b)2007744-0 DFG 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. oai:juser.fz-juelich.de:978443 authority:GRANT authority G AUTHORITY oai:juser.fz-juelich.de:978443