TU Ilmenau Humbold Bau

Projektdaten



Ausfallsicheres Broadcasting durch Unabhängige Spannbäume


Hochschule
TU Ilmenau
Fakultät/Einrichtung
Mathematik und Naturwissenschaften
Förderkategorie
DFG
Zeitraum
2018 - 2021
Drittmittelgeber
Deutsche Forschungsgemeinschaft
Bewilligungssumme, Auftragssumme
275.688,00 €

Abstract:

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.
Projektsuche | Impressum | FAQ