In this thesis, we present two e cent algorithms to compute shortest path between pair of vertices in directed and undirected double-loop networks. The algorithm for undirected double-loop networks is based on the concept "packed basis" proposed by Janez Zerrovnik and Toma z Pisanski. With O(logN) preprocessing time, both algorithms need only constant time to compute the shortest path between any pair of vertices in the network. This is an improvement of the best known algorithm, which needs O(l) time, where l is the length of the path in the directed double-loop networks. These algo- rithms are useful in message routing in the double-loop networks. Once the network has been constructed, the parameters for computing the shortest paths can be computed. At the time a message is to be delivered, the algo- rithm needs only constant time to determine which edge the message should be sent.

Abstract ¡@¡@Double-loop networks have become one of the most popular architectures in the design of Local Area Networks and distributed memory multiprocessor systems. This is due to its characters of minimal diameter, easy routing, expandability and regularity. The switching mechanism at each node can easily be implemented using building blocks of the same specification. Therefore, double-loop networks have a high degree of reliability and hence very low vulnerability. Let N denote the number of nodes in a double-loop network and d(N) be the best possible diameter with N vertices. Given an N, Bermond et al. [5], Boesch and Wang [7], and Yebra et al. [23] have shown that . This is a well-known lower bound for d(N) and is usually denoted as lb(N). In this paper, what we discuss is finding an optimal topology such that d(N)= lb(N) for any given value of N. We provide a simple formula to find optimal topologies of double-loop networks with N nodes.