Routing for generalized chordal rings

Bruce W. Arden; Kit Ming W. Tang

doi:10.1145/100348.100390

Routing for generalized chordal rings

Bruce W. Arden
, Kit Ming W. Tang

Electrical Engineering

University of Rochester

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Scopus citations

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 2^l where l is the smallest integer that such a path exists. Note that l ≲ d where d satisfies 2^d-1 < diameter ≲ 2^d. The inherent symmetry and the modular arthimetic connectivity of the GCR are exploited to achieve a parallel time complexity of O(log₂ diameter) and a serial time complexity of O(diameter).

Original language	English
Title of host publication	ACM Eighteenth Annual Computer Science Conference (CSC90)
Publisher	Publ by ACM
Pages	271-275
Number of pages	5
ISBN (Print)	0897913485, 9780897913485
DOIs	https://doi.org/10.1145/100348.100390
State	Published - 1990
Event	Cooperation 1990 ACM 18th Annual Computer Science Conference Proceedings - Washington, DC, USA Duration: Feb 20 1990 → Feb 22 1990

Publication series

Name	ACM Eighteenth Annual Computer Science Conference (CSC90)

Conference

Conference	Cooperation 1990 ACM 18th Annual Computer Science Conference Proceedings
City	Washington, DC, USA
Period	02/20/90 → 02/22/90

Access to Document

10.1145/100348.100390

Cite this

@inproceedings{b6451517591745b9af1f978e0d3ea2c1,

title = "Routing for generalized chordal rings",

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 arthimetic connectivity of the GCR are exploited to achieve a parallel time complexity of O(log2 diameter) and a serial time complexity of O(diameter).",

author = "Arden, \{Bruce W.\} and Tang, \{Kit Ming W.\}",

year = "1990",

doi = "10.1145/100348.100390",

language = "English",

isbn = "0897913485",

series = "ACM Eighteenth Annual Computer Science Conference (CSC90)",

publisher = "Publ by ACM",

pages = "271--275",

booktitle = "ACM Eighteenth Annual Computer Science Conference (CSC90)",

note = "Cooperation 1990 ACM 18th Annual Computer Science Conference Proceedings ; Conference date: 20-02-1990 Through 22-02-1990",

}

TY - GEN

T1 - Routing for generalized chordal rings

AU - Arden, Bruce W.

AU - Tang, Kit Ming W.

PY - 1990

Y1 - 1990

N2 - 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 arthimetic connectivity of the GCR are exploited to achieve a parallel time complexity of O(log2 diameter) and a serial time complexity of O(diameter).

AB - 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 arthimetic connectivity of the GCR are exploited to achieve a parallel time complexity of O(log2 diameter) and a serial time complexity of O(diameter).

UR - https://www.scopus.com/pages/publications/0025238365

U2 - 10.1145/100348.100390

DO - 10.1145/100348.100390

M3 - Conference contribution

AN - SCOPUS:0025238365

SN - 0897913485

SN - 9780897913485

T3 - ACM Eighteenth Annual Computer Science Conference (CSC90)

SP - 271

EP - 275

BT - ACM Eighteenth Annual Computer Science Conference (CSC90)

PB - Publ by ACM

T2 - Cooperation 1990 ACM 18th Annual Computer Science Conference Proceedings

Y2 - 20 February 1990 through 22 February 1990

ER -

Routing for generalized chordal rings

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this