completely independent spanning trees in large networksa difficult combinatorial problem with graphs and trees
What are CIST ?
The concept of Completely Independent Spanning Trees (CIST) was introduced by T. Hasunuma in addition to previous work on independent spanning trees, and finds applications in many network operations (routing protocols, layer 2 loops avoidance mechanisms, load balancing, robustness in case of failure).
Given a network topology described by a graph (a set of nodes and direct links), we aim to find a collection of spanning trees such that any pair of trees do not share any common link or inner node (that is to say any inner node in one tree is a leaf in all the others).
Computing a set of CIST is a difficult combinatorial problem, even a very difficult one. Given a network, it is hard to determine the size of the largest collection of CIST that exists on it, and even if at least two CIST may be found.
What we try to do is to have a better understanding of this problem : what makes it difficult to solve? Can we solve it easily on restricted networks topologies and how? Does there exist in some networks an algorithm allowing to compute a collection of CIST of sufficient size for networks operation, even if not optimal …
Our results so far
- 2 international jounal in combinatorics
- 1 international conference in combinatorics
- 1 national conference (french) in networks
People involved in the project
- Nicolas Gastineau
- Benoit Darties
- Olivier Togni