Tree-like decompositions of graphs and structures and their applications

Die 1984 von Robertson und Seymour eingeführten Baumzerlegungen von Graphen spielen eine wichtige Rolle sowohl in der modernen Graphentheorie als auch bei der Entwicklung und Analyse von Graphenalgorithmen. In den vergangen Jahren wurden neben Baumzerlegungen noch eine Reihe weiterer "baumartiger"
Zerlegungen von Graphen untersucht. Eine Theorie derartiger Zerlegungen von
Hypergraphen und allgemeineren relationalen Strukturen steckt hingegen noch in
den Kinderschuhen und soll ein zentraler Gegenstand dieses Projekts sein. Die
Frage nach Zerlegungen allgemeiner Strukturen wurde bei der Untersuchung von
bedeutenden algorithmischen Fragestellungen aus der künstlichen Intelligenz
und der Datenbanktheorie aufgeworfen, die hier zu entwickelnde Theorie soll zur
Lösung oder mindestens zu einem tieferen Verständnis dieser Fragen führen.



Im Projekt soll auch ein konkretes algorithmisches Problem, das
Isomorphieproblem für Graphen und allgemeinere Strukturen, untersucht werden.
Wir wollen die oben beschriebene Zerlegungstheorie anwenden, um bessere
Isomorphiealgorithmen für im weitesten Sinne baumartige Strukturen zu
entwickeln. Ein weiteres wichtiges, aus der Datenbanktheorie kommendes
Problem ist die Frage, ob es eine Sprache (eine "Logik") gibt, in der sich
gerade genau die effizient (in Polynomialzeit) beantwortbaren Anfragen an eine
Datenbank formulieren lassen. Dieses Problem hängt eng mit dem
Isomorphieproblem zusammen und soll ebenfalls in diesem Rahmen untersucht
werden.


Principal Investigators
Grohe, Martin Prof. Dr. (Details) (Theoretical Computer Science)

Financer
DFG: Sachbeihilfe

Duration of Project
Start date: 06/2006
End date: 05/2008

Last updated on 2020-09-03 at 23:16