Advertisement
Published in:
2019 | OriginalPaper | Chapter
Designing an Algorithm to Improve the Diameters of Completely Independent Spanning Trees in Crossed Cubes
Author : Kung-Jui Pai
Published in: New Trends in Computer Technologies and Applications
Publisher: Springer Singapore
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
Let T1, T2 be spanning trees in a graph G. If for any two vertices u, v of G, the paths from u to v in T1, T2 are vertex-disjoint except end vertices u and v, then T1, T2 are called two completely independent spanning trees (CISTs for short) in Pai and Chang [12] proposed an approach to recursively construct two CISTs in several hypercube-variant networks, including crossed cubes. For every kind of n-dimensional variant cube, the diameters of two CISTs for their construction are 2n − 1. In this paper, we give a new algorithm to construct two CISTs T1 and T2 in n-dimensional crossed cubes, and show that diam(T1) = diam(T2) = 2n − 2 if n ∈ {4,5}; and diam(T1) = diam(T2) = 2n − 3 if n ≥ 6 where diam(G) is the diameter of graph G.