(2020-2023, funded by DFG, principal investigator: Dr. Jens M. Schmidt)

A 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.

This project aims at attacking the Edge-Independent Spanning Tree Conjecture for higher k. 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.