Research On The Embedding Of Independent Spanning Trees Into Twisted Cubes And Parity Cubes

Parallel computing is becoming more and more important in many areas, such as sci-entific research, education, petroleum, meteorology and so on. Multiprocessor intercon-nect networks (in brief, interconnection networks) play critical roles in parallel computingsystems. An interconnection network can be represented by a graph, where a vertex is aprocessor and an edge is a communication link between the processors.The graph embedding ability of an interconnection network (host graph) is an indicatorof how efciently parallel algorithms with regular task graphs (guest graphs) can be exe-cuted on this network. An ideal interconnection network (host graph) is supposed to possessexcellent graph embedding ability.Considering graph G=(V, E), two spanning trees T1and T2of G are independent ifthey satisfy the following conditions:(1) T1and T2are rooted at the same vertex, say r,and (2) for each vertex v (r) in G, the path P from v to r in T1and the path Q from vto r in T2are disjoint, i.e. E(P)∩E(Q)=and V(P)∩V(Q)={v, r}. A set of spanningtrees of G are independent spanning trees if they are pairwise independent. Independentspanning trees have applications in networks such as reliable communication protocols, one-to-all broadcasting, and secure message distribution. Thus, the embedding of independentspanning trees into several classes of networks has been widely investigated.However, there is a conjecture on independent spanning trees: n independent spanningtrees rooted at an arbitrary vertex can be embedded into any n-connected graph. The con-jecture has been confirmed only for n-connected graphs with n≤4, and is still open forarbitrary n-connected graph when n≥5. In general it is very hard to embed n independentspanning trees rooted at an arbitrary vertex into a given n-connected graph. However, byproviding the construction schemes of independent spanning trees, the conjecture has beenproved to hold for several restricted classes of graphs.The twisted cube and parity cube are two important variants of the hypercube, and havemany features superior to those of hypercube. For example, the diameter of n-dimensionaltwisted cube (resp., parity cube) is about half of the diameter of the n-dimensional hyper- cube. In this thesis, we will study the embedding of a set of independent spanning treesinto twisted cubes and parity cubes, thus we confirm the conjecture of independent spanningtrees on twisted cubes and parity cubes. Furthermore, we analyze two properties of the in-dependent spanning trees constructed by our methods: isomorphism and height. Finally, wepropose an efcient parallel algorithm to construct independent spanning trees isomorphicto binomial-like trees on twisted cubes (resp., parity cubes).The major contributions are listed as follows.1. Embed n independent spanning trees into n-dimensional twisted cube (T Qn):(1) We improve the definition of twisted cubes, which extends the dimensions of twistedcubes to all the positive integers.(2) We prove that n independent spanning trees rooted at any vertex can be embeddedinto T Qnand present a recursive construction method to construct the n independent span-ning trees, thus we confirm the conjecture of independent spanning trees on twisted cubes.(3) We prove that all independent spanning trees constructed by our construction methodare isomorphic and the height of each tree is n+1for any integer n≥2.(4) We give an O(NlogN) recursive algorithm to embed n independent spanning treesrooted at any vertex into T Qn, where N denotes the number of vertices in T Qn.2. Embed n independent spanning trees into n-dimensional parity cube (PQn):(1) We give an O(N log N) recursive algorithm which can obtain n independent span-ning trees rooted at an arbitrary vertex on PQnand prove the correctness, thus we confirmthe conjecture of independent spanning trees on parity cubes.(2) We prove that all independent spanning trees obtained from our algorithm are iso-morphic.(3) We prove that for n≥2, the height of each independent spanning tree rooted at anyvertex on PQnis n+1.3. Parallel embedding of disjoint binomial-like spanning trees into twisted cubes andparity cubes.Since the above recursive algorithms forbid the possibility that the algorithms could beparallelized, we present a parallel algorithm to embed disjoint binomial-like spanning treesinto twisted cube (resp., parity cube), where disjoint binomial-like spanning trees are theindependent spanning trees isomorphic to binomial-like trees.(1) We present an algorithm to embed n disjoint binomial-like spanning trees rooted atan arbitrary vertex on PQnand prove the correctness. The algorithm can be parallelized in O(N) time, where N=2n.(2) An O(N) parallel algorithm is presented to embed n disjoint binomial-like spanningtrees rooted at an arbitrary vertex on T Qn, where N denotes the number of vertices in T Qn.