Routing for generalized chordal rings

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Routing for generalized chordal rings

Full text

Pdf (411 KB)

Source

ACM Annual Computer Science Conference archive
Proceedings of the 1990 ACM annual conference on Cooperation table of contents

Washington, D.C., United States

Pages: 271 - 275

Year of Publication: 1990

ISBN:0-89791-348-5

Authors

Bruce W. Arden	Department of Electrical Engineering, University of Rochester, Rochester NY
Kit-Ming W. Tang	Department of Electrical Engineering, University of Rochester, Rochester NY

Sponsor

ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 10, Citation Count: 3

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/100348.100390 What is a DOI?

ABSTRACT

A recursive routing algorithm is presented for generalized chordal ring (GCR) graphs. This algorithm consists of two parts. The first part deals with an one-time establishment of a database, and the second part determines a path of length less than or equal to 2l where l is the smallest integer that such a path exists. Note that l ≤ d where d satisfies 2d-1 < diameter ≤ 2d. The inherent symmetry and the modular arithmetic connectivity of the GCR are exploited to achieve a parallel time complexity of O(log2 diameter) and a serial time complexity of O(diameter).

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A.J. Hoffman and R.R. Singleton. "On Moore Graphs with Diameters 2 and 3". IBM Journal, 30:497-504, November 1960.
	2	J.-C. Bermond , C. Delorme , J.-J. Quisquater, Strategies for interconnection networks: some methods from graph theory, Journal of Parallel and Distributed Computing, v.3 n.4, p.433-449, December 1, 1986 [doi>10.1016/0743-7315(86)90008-0]
	3	D.V. Chudnovsky, G.V. Chudnovsky, and M.M. Denneau. Regular graphs with small diameter as models for interconnection networks. Technical Report RC 13484(60281), IBM Research Division, February 1988.
	4	B.W. Arden and K.W. Tang. Representation and Routing of Cayley Graphs. Technical Report EL-89- 02, Department of ElectirM Engineering, University of Rochester, 1989.

CITED BY 3

	K. Wendy Tang , Bruce W. Arden, Vertex-transitivity and routing for Cayley graphs in GCR representations, Proceedings of the 1992 ACM/SIGAPP symposium on Applied computing: technological challenges of the 1990's, p.1180-1187, March 1992, Kansas City, Missouri, United States
	Behrooz Parhami , Ding-Ming Kwai, Periodically Regular Chordal Rings, IEEE Transactions on Parallel and Distributed Systems, v.10 n.6, p.658-672, June 1999
	A. Chadi Aljundi , Jean-Luc Dekeyser , M-Tahar Kechadi , Isaac D. Scherson, A universal performance factor for multi-criteria evaluation of multistage interconnection networks, Future Generation Computer Systems, v.22 n.7, p.794-804, August 2006