Independent Spanning Trees in Networks – A Survey

What is it about?

The problem of constructing independent spanning trees (ISTs) dates back to as early as late 1980s. Given a network G of a certain topology, the question is whether we can, as well as how to, construct a set of independent spanning trees in G. ISTs have proven to be of great importance in many network tasks. The past decade has seen a particularly remarkable increase in the literature on ISTs, manifesting a significant growth of interest. ISTs can be classified into edge-independent spanning trees (edge-ISTs), node-independent spanning trees (node-ISTs), and completely independent spanning trees (CISTs). For a network G, node-ISTs (edge-ISTs) rooted at u are a set of spanning trees rooted at u in G such that there are no common internal nodes (edges) between u and any other node among the paths in these spanning trees. If every node in a set of node-ISTs can act as a root node, the set of trees are called CISTs.

Featured Image

Photo by Clint Adair on Unsplash

Photo by Clint Adair on Unsplash

Why is it important?

This survey aims at bringing together important works on ISTs that have been reported in the literature. It provides a historical perspective of how the field has evolved, and can serve as an integrated useful resource of references for future research on ISTs.

Perspectives