On the Fault Tolerance and Hamiltonicity of the Optical Transpose Interconnection System of Non-Hamiltonian Base Graphs

Details On the Fault Tolerance and Hamiltonicity of the Optical Transpose Interconnection System of Non-Hamiltonian Base Graphs On the Fault Tolerance and Hamiltonicity of the Optical Transpose Interconnection System of Non-Hamiltonian Base Graphs

2011-09-08

arxiv.org/abs/1109.1706v1

Computer Science

Distributed, Parallel, and Cluster Computing

Scientific paper

Hamiltonicity is an important property in parallel and distributed computation. Existence of Hamiltonian cycle allows efficient emulation of distributed algorithms on a network wherever such algorithm exists for linear-array and ring, and can ensure deadlock freedom in some routing algorithms in hierarchical interconnection networks. Hamiltonicity can also be used for construction of independent spanning tree and leads to designing fault tolerant protocols. Optical Transpose Interconnection Systems or OTIS (also referred to as two-level swapped network) is a widely studied interconnection network topology which is popular due to high degree of scalability, regularity, modularity and package ability. Surprisingly, to our knowledge, only one strong result is known regarding Hamiltonicity of OTIS - showing that OTIS graph built of Hamiltonian base graphs are Hamiltonian. In this work we consider Hamiltonicity of OTIS networks, built on Non-Hamiltonian base and answer some important questions. First, we prove that Hamiltonicity of base graph is not a necessary condition for the OTIS to be Hamiltonian. We present an infinite family of Hamiltonian OTIS graphs composed on Non-Hamiltonian base graphs. We further show that, it is not sufficient for the base graph to have Hamiltonian path for the OTIS constructed on it to be Hamiltonian. We give constructive proof of Hamiltonicity for a large family of Butterfly-OTIS. This proof leads to an alternate efficient algorithm for independent spanning trees construction on this class of OTIS graphs. Our algorithm is linear in the number of vertices as opposed to the generalized algorithm, which is linear in the number of edges of the graph.

Affiliated with

Also associated with

No associations

Rating

On the Fault Tolerance and Hamiltonicity of the Optical Transpose Interconnection System of Non-Hamiltonian Base Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Fault Tolerance and Hamiltonicity of the Optical Transpose Interconnection System of Non-Hamiltonian Base Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Fault Tolerance and Hamiltonicity of the Optical Transpose Interconnection System of Non-Hamiltonian Base Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-475152