4.6 Article

The Construction of Multiple Independent Spanning Trees on Burnt Pancake Networks

期刊

IEEE ACCESS
卷 9, 期 -, 页码 16679-16691

出版社

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/ACCESS.2021.3049290

关键词

Independent spanning trees; burnt pancake network; interconnection networks; fault-tolerant transmission; secure message distribution

资金

  1. Constructing Independent Spanning Trees on Some Networks [MOST 109-2221-E-006-165]

向作者/读者索取更多资源

The concept of independent spanning trees has significant implications in graph theory, studying the applications of multiple spanning trees in networks, such as fault-tolerant transmission and secure message distribution in communication networks. This paper proposes a scheme for constructing independent spanning trees on a burnt pancake network and proves the correctness of the algorithm.
A set of the spanning trees in a graph G is called independent spanning trees if they have a common root r and for each vertex nu is an element of V (G) \ {r}, the paths from nu to r in any two trees are directed edge-disjoint and internally vertex-disjoint. The construction of independent spanning trees has many practical applications in reliable communication networks, such as fault-tolerant transmission and secure message distribution. A burnt pancake network BPn is a kind of Cayley graph, which has been proposed as the topology of an interconnection network. In this paper, we provide a two stages construction scheme that can be used to construct a maximal number of independent spanning trees on a burnt pancake network in O(Nxn) time, where N is the number of nodes of BPn and n is the dimension of the network. Furthermore, we prove the correctness of our proposed algorithm in constructing independent spanning trees.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.6
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据