completely independent spanning trees in large networks

a 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).

The challenge

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

Interested In Working With Us?