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

fYear

1997

fDate

17-21 Mar 1997

Firstpage

104

Lastpage

110

Abstract

We study the problem of performing all-to-all broadcast on an n-alternating group graph AG_n with all-port and store-and-forward routing. The running time is [(n¹-2)/(4(n-2))+1] that is one step more than the trivial lower bound [(n²-2)/(4(n-2))]. Our algorithm is based on some new properties of Hamiltonian paths of AG_n 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;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel Algorithms/Architecture Synthesis, 1997. Proceedings., Second Aizu International Symposium

Conference_Location

Aizu-Wakamatsu

Print_ISBN

0-8186-7870-4

Type

conf

DOI

10.1109/AISPAS.1997.581639

Filename

581639