Record #261379 - GSI Repository

DFG project G:(GEPRIS)426003173

Grundlagen der effizienten Modellprüfung für Zähllogiken auf strukturell dünnen Graphklassen

Coordinator	Professor Dr. Peter Rossmanith
Grant period	2019 - 2023
Funding body	Deutsche Forschungsgemeinschaft
	DFG
Identifier	G:(GEPRIS)426003173

Note: Viele 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.

Recent Publications

There are no publications

Record created 2023-01-19, last modified 2024-09-28

Similar records

Add to personal basket
Export as Author List with IDs BibTeX (UTF-8), EndNote XML, EndNote Text, RIS, MARC, Print MARC, MARCXML, DC,
Request correction
Submit fulltext

GSI Homepage \| GSI Library \| English Deutsch \| guest :: login GSI Repository
Search	Submit	Personalize Your alerts Your baskets Your searches	Help