Restricted Shortest Paths for Routing in 2-circulant Networks

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

Keywords

Communication Algorithms, Interconnection Networks,Two-Terminal Message Routing

Abstract

A double-loop network G(n;h₁,h₂) is a directed graph where the node set is Z_n and the edge set is the union of sets E_i={(u,u+h_i (mod n)) | uЄ Z_n}, 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 E_i. 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:

• DOI:
• From Proceeding (381) Communications and Computer Networks - 2002

Go Back