EUVIMEDEUVIMED entdecken
Crossref

Independent Spanning Trees in Networks: A Survey

Baolei Cheng, Dajin Wang, Jianxi Fan

ACM Computing Surveys · 31.12.2023 · 55 (14s) · 1-29

DOI: 10.1145/3591110 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Computing Surveys, online erschienen am 17.07.2023. Verfasst von Baolei Cheng und 2 weiteren Autor:innen. Die Arbeit wurde bisher 39-mal zitiert (Crossref) und nennt 131 Literaturangaben. Gefördert von: National Natural Science Foundation of China, Jiangsu Province Department of Education Future Network Scientific Research Fund Project, Priority Academic Program Development of Jiangsu Higher Education Institutions.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • National Natural Science Foundation of China
  • Jiangsu Province Department of Education Future Network Scientific Research Fund Project
  • Priority Academic Program Development of Jiangsu Higher Education Institutions
  • Collaborative Innovation Center of Novel Software Technology and Industrialization

Zitieren

APA

Cheng, B., Wang, D., & Fan, J. (2023). Independent Spanning Trees in Networks: A Survey. ACM Computing Surveys, 55(14s), 1-29. https://doi.org/10.1145/3591110

Vancouver

Cheng B, Wang D, Fan J. Independent Spanning Trees in Networks: A Survey. ACM Computing Surveys. 2023;55(14s):1-29. doi:10.1145/3591110

BibTeX
@article{Cheng2023,
  author = {Cheng, Baolei and Wang, Dajin and Fan, Jianxi},
  title = {Independent Spanning Trees in Networks: A Survey},
  journal = {ACM Computing Surveys},
  year = {2023},
  volume = {55},
  number = {14s},
  pages = {1--29},
  doi = {10.1145/3591110}
}
Kostenlos starten →