Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952186 | Theoretical Computer Science | 2017 | 10 Pages |
Abstract
Edge-independent spanning trees (EISTs) have important applications in networks such as reliable communication protocols, one-to-all broadcasting, and secure message distribution, thus their designs in several classes of networks have been widely investigated. The n-dimensional augmented cube (AQn) is an important variant of the n-dimensional hypercube. It is (2nâ1)-regular, (2nâ1)-connected (nâ 3), vertex-symmetric and has diameter of ân/2â. In this paper, by proposing an O(Nlogâ¡N) algorithm that constructs 2nâ1 EISTs in AQn, where N is the number of nodes in AQn, we solve the EISTs problem for this class of graphs. Since AQn is (2nâ1)-regular, the result is optimal with respect to the number of EISTs constructed.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Yan Wang, Hong Shen, Jianxi Fan,