000261379 001__ 261379
000261379 005__ 20240928175432.0
000261379 0247_ $$aG:(GEPRIS)426003173$$d426003173
000261379 035__ $$aG:(GEPRIS)426003173
000261379 040__ $$aGEPRIS$$chttp://gepris.its.kfa-juelich.de
000261379 150__ $$aGrundlagen der effizienten Modellprüfung für Zähllogiken auf strukturell dünnen Graphklassen$$y2019 - 2023
000261379 371__ $$aProfessor Dr. Peter Rossmanith
000261379 450__ $$aDFG project G:(GEPRIS)426003173$$wd$$y2019 - 2023
000261379 5101_ $$0I:(DE-588b)2007744-0$$aDeutsche Forschungsgemeinschaft$$bDFG
000261379 680__ $$aViele Entscheidungs- und Optimierungsprobleme auf Graphen und Datenbanken lassen sich in geeigneten Logiken ausdrücken.Meta-Algorithmen sind Algorithmen, die nicht auf ein bestimmtes Problem beschränkt sind. Sie können alle Probleme lösen, die sich durch gewisse logische Formeln ausdrücken lassen, was sie zu einem sehr flexiblem Werkzeug macht.Es sind bereits mehrere solcher Meta-Algorithmen bekannt. Für die Prädikatenlogik erster Stufe können entsprechende Probleme effizient auf bestimmten Graphklassen gelöst werden, sofern diese Graphklassen gewisse strukturelle Eigenschaften besitzen. Für die ausdrucksstärkere monadische Logik zweiter Ordnung gibt es ebenfalls solche Algorithmen, welche aber nur auf stärker eingeschränkten Graphklassen arbeiten.In Zählproblemen spielen die Anzahl und Größe verschiedener Mengen eine Rolle. Sie können in klassischer Prädikatenlogik nicht oder nur eingeschränkt modelliert werden, spielen aber in der Praxis eine wichtige Rolle. Um Zählprobleme zu modellieren, können entsprechende Zähllogiken definiert werden. Aus den letzten Jahren gibt es auch auf diesem Gebiet einige Ergebnisse, wobei aber viele Fragen noch offen blieben.In diesem Projekt soll untersucht werden, welche Zählprobleme auf welchen Graphklassen durch Meta-Algorithmen effizient gelöst werden können. Dabei wollen wir zwischen exaktem und approximativem Zählen unterscheiden und auch verwandte Themen wie Aufzählalgorithmen behandeln. Neben dem Entwurf effizienter Algorithmen sollen auch stets passende untere Schranken bewiesen werden. Dieses Vorgehen soll mit den folgenden drei Problemen als Grundstein begonnen werden:Wir wollen eine aussagekräftige Zähllogik betrachten, für die bereits bekannt ist, dass man sie auf sehr beschränkten Graphklassen nicht exakt auswerten kann. Für diese Logik wollen wir einen aproximativen Auswertungsalgorithmus entwickeln.Des weiteren wollen wir Meta-Algorithmen für Zählprobleme mit Paritätsbedingungen angeben, indem wir die Erweiterung der Prädikatenlogik um Modulo-Zählen untersuchen.Das Problem Partial Dominating Set sucht nach einer Menge von Knoten, die die Hälfte des Graphen dominieren. Wir betrachten eine Zähllogik, die dieses und ähnliche Probleme beschreiben kann. Auf diese Weise wollen wir verschiedene Dominierungs- und Überdeckungsprobleme auf möglichst allgemeinen Graphklassen effizient lösen.
000261379 909CO $$ooai:juser.fz-juelich.de:927982$$pauthority$$pauthority:GRANT
000261379 909CO $$ooai:juser.fz-juelich.de:927982
000261379 980__ $$aG
000261379 980__ $$aAUTHORITY