Minimum 2-terminal routing in 2-jump circulant graphs

Authors

  • B. Robič
  • J. Žerovnik

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 ± h1(mod n), u ± h2(mod n), where O < h1 < h2 < n. An algorithm for routing a packet along the shortest path between a pair of processors in 2-jump circulant network is given. The algorithm requires Q(d) time for preprocessing, and l routing steps, where d is the diameter of the graph and l = O(d) is the distance between the two processors.

Downloads

Download data is not yet available.

Published

2012-03-01

How to Cite

Robič, B., & Žerovnik, J. (2012). Minimum 2-terminal routing in 2-jump circulant graphs. COMPUTING AND INFORMATICS, 19(1), 37–46. Retrieved from https://www.cai.sk/ojs/index.php/cai/article/view/552