Theorie und Algorithmen für Zusammenhang in Graphen mit Maximum Adjacency Orderings

• Antragsteller: Professor Dr. Jens M. Schmidt
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2015 bis 2019
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 270450205

Eine fundamentale Eigenschaft eines Graphen ist sein Zusammenhang: Wird ein Graph beispielsweise als Wegenetz interpretiert, fragt der Zusammenhang nach der maximalen Anzahl von disjunkten Wegen zwischen jedem Städtepaar.In der theoretischen Informatik existiert eine Vielzahl von Algorithmen, die den Zusammenhang traditionell mit Hilfe von Flussnetzwerken berechnen. In den letzten Jahren ist aber eine alternative Methode zur Berechnung des Zusammenhangs immer wichtiger geworden, die komplett ohne Flussnetzwerke auskommt: Der Einsatz von sogenannten Maximal Adjacency Orderings. Diese sind insofern bemerkenswert, dass sie mehrere klassische Resultate aus der strukturellen Graphentheorie nicht nur wesentlich einfacher als die Originalbeweise herleiten lassen, sondern sogar verallgemeinern können. Solche fruchtbaren Rückbezüge zur diskreten Mathematik haben historisch gesehen oft zu weitreichenden Erkenntnisgewinnen in beiden Welten geführt.Das Ziel dieses Projektes ist, Maximal Adjacency Orderings sowohl graphentheoretisch auf strukturelle Erkenntnisse über den Zusammenhang zu untersuchen als auch die Anwendbarkeit dieser Strukturen für effizientere und einfachere Algorithmen auszuloten.

• DFG-Verfahren: Sachbeihilfen