Title :
Node Mapping Algorithm between Hypercube and Petersen-Torus Networks
Author :
Jung-hyun Seo ; HyeongOk Lee ; Moon-suk Jang ; EungKon Kim
Author_Institution :
Dept. of Comput. Eng., Nat. Univ. of Sunchon, Sunchon
Abstract :
In this study, it was proven that hypercube interconnection network whose degree increases with increased dimensions might be embedded into PT network whose degree is fixed. Hypercube Q log 2 n2+3 was embedded into PT(n,n) at expansion 10/8, dilation 1.5n+2, and congestion 4 n. The mapping algorithm was designed for expansion to approach 1, and congestion and dilation are in proportion to O(n) owing to the aspect of hypercube that the degree increases.
Keywords :
graph theory; hypercube networks; parallel algorithms; Petersen-Torus network; hypercube interconnection network; node mapping algorithm; parallel algorithm; undirected graph; Algorithm design and analysis; Appropriate technology; Communication switching; Computer networks; Hypercubes; Information management; Information technology; Multiprocessor interconnection networks; Parallel algorithms; Tree graphs; Embedding; Hypercube; Interconnection Network; Petersen-Torus;
Conference_Titel :
Networked Computing and Advanced Information Management, 2008. NCM '08. Fourth International Conference on
Conference_Location :
Gyeongju
Print_ISBN :
978-0-7695-3322-3
DOI :
10.1109/NCM.2008.49
