Minimum 2-terminal routing in 2-jump circulant graphs

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.