期刊
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
资金
- 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据