Name
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). |
Year | DOI | Venue |
|---|---|---|
1990 | 10.1145/100348.100390 | ACM Conference on Computer Science |
Keywords | Field | DocType |
recursive routing algorithm,inherent symmetry,parallel time complexity,smallest integer,generalized chordal ring,one-time establishment,modular arithmetic connectivity,serial time complexity,log2 diameter,part deal,time complexity,satisfiability,modular arithmetic | Integer,Discrete mathematics,Graph,Modular arithmetic,Computer science,Chordal graph,Algorithm,Theoretical computer science,Time complexity,Recursion,Routing algorithm | Conference |
ISBN | Citations | PageRank |
0-89791-348-5 | 6 | 0.78 |
References | Authors | |
2 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bruce W. Arden | 1 | 365 | 474.14 |
| Kit-Ming W. Tang | 2 | 6 | 0.78 |