2023-06-252023-06-25https://tore.tuhh.de/handle/11420/16479A classic theoretical measure for the resilience of a communication network is its edge-connectivity. However, for some network problems, this measure is not known to be suitable at all. In resilient broadcasting, for example, one prescribed vertex r communicates with every other vertex through a set of spanning trees such that, for every vertex v, the paths from r to v in these spanning trees are edge-disjoint (such trees are called independent). But it is unknown how exactly the maximal number of independent spanning trees in a network relate to its edge-connectivity, and nothing more is known for the analogous question regarding vertex-failures or for the complexity of finding such independent spanning trees.In fact, the long-standing Edge-Independent Spanning Tree Conjecture in graph theory states that every k-edge-connected network contains k independent spanning trees. A proof of this conjecture would not only characterize the networks in which resilient broadcasting is possible, but arguably also deliver the structural insights that are necessary for the compact design of such networks and for efficient routing schemes in these. Although there is recent structural and algorithmic progress on this conjecture for small k (in which case the conjecture is true), a generalization to higher k was not achieved so far.This project aims at attacking the Edge-Independent Spanning Tree Conjecture for higher k, using the recently proposed structures. We will use graph-theoretic methods in order to search for the right generalization to higher k but also computer-assisted algorithms to support this search.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.