Zerlegungen, Tangles und Cluster

• Antragsteller: Professor Dr. Martin Grohe
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2019 bis 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 414230410

Baumzerlegungen beschreiben, wie sich ein Graph in weitgehend unabhängige Teile zerlegen lässt. Mittlerweile sind Baumzerlegungen zu einem Standardwerkzeug der Algorithmik mit Anwendungen in vielen Bereichen der Informatik geworden. In der strukturellen Graphentheorie wurden verschiedene zu Baumzerlegungen duale Konzepte vorgeschlagen, die intuitiv "stark zusammenhängende Regionen" in Graphen beschreiben. Am wichtigsten unter diesen sind wohl Tangles. Obwohl weit weniger bekannt als Baumzerlegungen, haben Tangles und ähnliche Objekte ebenfalls eine Reihe von Anwendungen in der Informatik, und sie scheinen noch ein großes Potential für zukünftige Anwendungen zu haben. Eine noch kaum erforschte Idee ist es, Tangles im Bereich Clustering zu verwenden. Diese Idee geht auf einen Vorschlag von Diestel und Whittle zurück, die dabei vor allem Image-Segmentation Probleme im Sinn hatten.Ziel diese Projekts ist eine Verallgemeinerung der Theorie von Zerlegungen und Tangles im Hinblick auf Anwendungen in den Bereichen Clustering und Constraint Satisfaction. In technischer Sicht verlangt dies zum einen eine Erweiterung von ganzzahligen auf reelwertige Zusammenhangsmaße, die es uns erlaubt, die Theorie auf durch reelle Vektoren repräsentierte Daten anzuwenden, und zum anderen eine Erweiterung auf neue, hybride Formen von Zerlegungen. Im Mittelpunkt unserer Untersuchungen werden algorithmische Fragestellungen stehen, die auch im bislang hauptsächlich untersuchten ganzzahligen Kontext noch ungenügend verstanden sind.

• DFG-Verfahren: Sachbeihilfen