Communication algorithms on alternating group graphs

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Chih-Ming Lai Articles by Jyh-Jong Tsay

2nd AIZU International Symposium on Parallel Algorithms / Architecture Synthesis (pAs '97)

Aizu-Wakamatsu, Fukushima, JAPAN

March 17-March 21

ISBN: 0-8186-7870-4

	ASCII Text	x
	Chih-Ming Lai, Jyh-Jong Tsay, "Communication algorithms on alternating group graphs," Parallel Algorithms / Architecture Synthesis, AIZU International Symposium on, pp. 104, 2nd AIZU International Symposium on Parallel Algorithms / Architecture Synthesis (pAs '97), 1997.

	BibTex	x
	@article{ 10.1109/AISPAS.1997.581639, author = {Chih-Ming Lai and Jyh-Jong Tsay}, title = {Communication algorithms on alternating group graphs}, journal ={Parallel Algorithms / Architecture Synthesis, AIZU International Symposium on}, volume = {0}, year = {1997}, isbn = {0-8186-7870-4}, pages = {104}, doi = {http://doi.ieeecomputersociety.org/10.1109/AISPAS.1997.581639}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Parallel Algorithms / Architecture Synthesis, AIZU International Symposium on TI - Communication algorithms on alternating group graphs SN - 0-8186-7870-4 SP EP A1 - Chih-Ming Lai, A1 - Jyh-Jong Tsay, PY - 1997 KW - multiprocessor interconnection networks; communication algorithms; alternating group graphs; all-to-all broadcast; all-port routing; store-and-forward routing; running time; lower bound; Hamiltonian paths; single-node scattering; time bound; multiprocessor interconnection networks; parallel algorithms; distributed memory systems VL - 0 JA - Parallel Algorithms / Architecture Synthesis, AIZU International Symposium on ER -

Chih-Ming Lai, Dept. of Comput. Sci. & Inf. Eng., Nat. Chung Cheng Univ., Chiayi, Taiwan

Jyh-Jong Tsay, Dept. of Comput. Sci. & Inf. Eng., Nat. Chung Cheng Univ., Chiayi, Taiwan

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/AISPAS.1997.581639

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

Index Terms:

multiprocessor interconnection networks; communication algorithms; alternating group graphs; all-to-all broadcast; all-port routing; store-and-forward routing; running time; lower bound; Hamiltonian paths; single-node scattering; time bound; multiprocessor interconnection networks; parallel algorithms; distributed memory systems

Citation:

Chih-Ming Lai, Jyh-Jong Tsay, "Communication algorithms on alternating group graphs," pas, pp.104, 2nd AIZU International Symposium on Parallel Algorithms / Architecture Synthesis (pAs '97), 1997

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.