On pancyclicity properties of OTIS-mesh

• Published in: Information processing letters 2011-03, Vol.111 (8), p.353-359
• Main Authors: Shafiei, T., Hoseiny-Farahabady, M.R., Movaghar, A., Sarbazi-Azad, H.
• Format: Article
• Language: English
• Subjects: Algorithmics. Computability. Computer arithmetics; Algorithms; Applied sciences; Computer networks; Computer science; control theory; systems; Cycle; Embedding; Exact sciences and technology; Graph theory; Graphs; Information retrieval. Graph; Interconnect; Interconnection networks; Mathematical problems; Miscellaneous; Networks; Optical interconnects; Optoelectronics; OTIS-mesh; Pancyclicity; Path; Studies; Theoretical computing
• ISSN: 0020-0190; 1872-6119
• DOI: 10.1016/j.ipl.2010.11.027

In optoelectronic OTIS multicomputer networks (also known as Swapped networks), electrical and optical interconnects are used for local and global communication, respectively. An interesting instance of the OTIS multicomputers is the OTIS-mesh. Pancyclicity is of great importance in the implementation of a variety of parallel algorithms in multicomputers. This paper addresses the Pancyclicity problem of OTIS-mesh. More precisely, we prove that if the factor graph G of an OTIS network is a 2-D or 3-D mesh with at least one even radix, OTIS- G can embed any cycle of length l, l ∈ { 4 , 6 , 7 , 8 , 9 , … , | G | 2 } . ► We use graph to model interconnection network. ► We prove pancyclicity in OTIS-mesh by considering two separate cases for 2-D and 3-D mesh for the factor graph G of OTIS-G. ► Using construction method it is showed that if G has N nodes and at least one dimension of even radix, then OTIS-G contains any cycle of length l ∈ { 4 , 6 , 7 , 8 , 9 , … , N 2 } .