Title :
Communication algorithms on alternating group graphs
Author :
Lai, Chih-Ming ; Tsay, Jyh-Jong
Author_Institution :
Dept. of Comput. Sci. & Inf. Eng., Nat. Chung Cheng Univ., Chiayi, Taiwan
Abstract :
We study the problem of performing all-to-all broadcast on an n-alternating group graph AGn with all-port and store-and-forward routing. The running time is [(n1-2)/(4(n-2))+1] that is one step more than the trivial lower bound [(n2-2)/(4(n-2))]. Our algorithm is based on some new properties of Hamiltonian paths of AGn that are identified in this paper and are of independent interest. Similar properties have been used to design an algorithm for single-node scattering that achieves the same time bound
Keywords :
computational complexity; distributed memory systems; graph theory; multiprocessor interconnection networks; network routing; parallel algorithms; Hamiltonian paths; all-port routing; all-to-all broadcast; alternating group graphs; communication algorithms; distributed memory systems; lower bound; multiprocessor interconnection networks; parallel algorithms; running time; single-node scattering; store-and-forward routing; time bound; Broadcasting; Computer science; Concurrent computing; Councils; Distributed computing; Hypercubes; Memory architecture; Parallel processing; Routing; Scattering;
Conference_Titel :
Parallel Algorithms/Architecture Synthesis, 1997. Proceedings., Second Aizu International Symposium
Conference_Location :
Aizu-Wakamatsu
Print_ISBN :
0-8186-7870-4
DOI :
10.1109/AISPAS.1997.581639
