Minimum 2-terminal routing in 2-jump circulant graphs

Authors
Robic, B Zerovnik, J
Citation
B. Robic et J. Zerovnik, Minimum 2-terminal routing in 2-jump circulant graphs, COMPUT A IN, 19(1), 2000, pp. 37-46
Citations number
15
Categorie Soggetti
Computer Science & Engineering
Journal title
COMPUTERS AND ARTIFICIAL INTELLIGENCE
ISSN journal
02320274 → ACNP
Volume
19
Issue
1
Year of publication
2000
Pages
37 - 46
Database
ISI
SICI code
0232-0274(2000)19:1<37:M2RI2C>2.0.ZU;2-A
Abstract
A 2-jump circulant is an undirected graph whose nodes are integers 0, 1,... , n - 1 and each node u is adjacent to four nodes u +/- h(1) (mod n), u +/- h(2) (mod n), where 0 < h(1) < h(2) < n. An algorithm for routing a packet along the shortest path between a pair of processors in 2-jump circulant n etworks is given. The algorithm requires -(d) time for preprocessing, and l routing steps, where d is the diameter of the graph and l = O(d) is the di stance between the two processors.