Independent Spanning Trees in Networks: A Survey

Baolei Cheng, Dajin Wang, Jianxi Fan

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

The problem of constructing independent spanning trees (ISTs) dates back to as early as the 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 ISTs 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 is called CISTs. 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.

Original languageEnglish
Article number335
JournalACM Computing Surveys
Volume55
Issue number14 S
DOIs
StatePublished - 17 Jul 2023

Keywords

  • Independent spanning trees (ISTs)
  • algorithms
  • edge-disjoint spanning trees
  • interconnection networks

Fingerprint

Dive into the research topics of 'Independent Spanning Trees in Networks: A Survey'. Together they form a unique fingerprint.

Cite this