Ausfallsicheres Broadcasting durch Unabhängige Spannbäume

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

Ein klassisches theoretisches Maß für die Ausfallsicherheit eines Netzwerks ist sein Kantenzusammenhang. Für manche praktisch relevanten Netzwerk-Probleme ist allerdings nicht bekannt, ob dieses Maß überhaupt zur Untersuchung der Ausfallsicherheit geeignet ist. So kommuniziert bei einem ausfallsicheren Broadcast beispielsweise ein festgelegter Knoten r zu allen anderen Knoten mit Hilfe von Spannbäumen, in denen für jeweils jeden Knoten v die Pfade von r nach v kantendisjunkt sind (solche Bäume heißen voneinander unabhängig). Es ist aber nicht bekannt, wie genau die Anzahl solcher unabhängigen Spannbäume von dem Kantenzusammenhang des Netzwerks abhängt, und für die analoge Fragestellung gegenüber dem Ausfall von Knoten oder auch nur der Komplexität, möglichst viele solcher unabhängigen Spannbäume zu finden, herrscht eine ähnliche Unwissenheit.Tatsächlich besagt eine fundamentale Vermutung der Graphentheorie, dass jedes k-kantenzusammenhängende Netzwerk k unabhängige Spannbäume enthält. Ein Beweis dieser Vermutung würde nicht nur charakterisieren, in welchen Netzwerken ausfallsichere Broadcasts überhaupt möglich sind, sondern aller Wahrscheinlichkeit nach auch die strukturellen Erkenntnisse liefern, die für das kompakte Design solcher Netzwerke und effizientes Routing in diesen notwendig sind. Obwohl kürzlich grundlegende strukturelle und algorithmische Fortschritte für kleines k zu obiger Vermutung erreicht worden sind (die Vermutung ist wahr für k höchstens 4), konnten diese noch nicht auf größeres k verallgemeinert werden.Das Ziel dieses Projekts ist, mit Hilfe der jüngsten strukturellen Fortschritte die unabhängige Spannbaum-Vermutung für größeres k zu attackieren. Dabei sollen nicht nur graphentheoretische Methoden sondern auch Algorithmen zur computer-unterstützten Struktursuche eingesetzt werden.

• DFG-Verfahren: Sachbeihilfen