Restricted Shortest Paths for Routing in 2-circulant Networks

T. Dobravec, B. Robič, and B. Vilfan (Slovenia)


Communication Algorithms, Interconnection Networks,TwoTerminal Message Routing


A double-loop network G(n;h1,h2) is a directed graph where the node set is Zn and the edge set is the union of sets Ei={(u,u+hi (mod n)) | uЄ Zn}, for i Є {1,2}. Changing directed links into undirected ones results in an undirected double-loop network, also called 2-circulant. A restricted shortest path between two nodes of a 2-circulant is any shortest path between the two nodes having no link in Ei. We describe an O(log n) algorithm that we conjecture calculates the restricted shortest paths. Unfortunately, we do not yet have a proof of its correctness, but extensive simulations have not uncovered a case where it fails. An application of this algorithm in fast two-terminal routing in 2-circulants is also described.

Important Links:

Go Back