Entwurf und Analyse impliziter BDD-basierter Graphalgorithmen

• Antragstellerin: Professorin Dr. Beate Bollig
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2010 bis 2015
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 173772243

Graphalgorithmen arbeiten üblicherweise auf expliziten Graphbeschreibungen wie Adjazenzlistenoder -matrizen. Bei der Analyse komplexer Systeme können jedoch so großeGraphen auftreten, dass herkömmliche Algorithmen kaum einsetzbar sind. Die Hoffnung,dass Struktureigenschaften typischer Anwendungsgraphen für eine komprimierte Darstellungausgenutzt werden können, führt zu impliziten Graphdarstellungen. Der Entwurf unddie Analyse symbolischer BDD-basierter Algorithmen ist in den letzten Jahren für verschiedeneGraphprobleme intensiver untersucht worden. Dabei hat sich bestätigt, dass sich ihreArbeitsweise wesentlich von derjenigen klassischer Algorithmen unterscheidet. Auch dieübliche worst case Analyse erscheint im Szenario impliziter Algorithmen unpassend. Hiersollen Entwurfsmethoden für symbolische BDD-basierte Graphalgorithmen weiterentwickeltund Analysemethoden verfeinert werden, insbesondere sollen differenziertere Technikengefunden werden, die den praktischen Erfolg der BDD-basierten Algorithmen erklärenkönnen. Das typische Verhalten symbolischer Algorithmen soll sowohl experimentell alsauch theoretisch untersucht werden. Daneben sollen auch dynamische Graphprobleme undApproximationsalgorithmen behandelt werden.

• DFG-Verfahren: Sachbeihilfen