Abstract | ||
---|---|---|
Loop networks with hop connections offer smaller diameter, path lengths, alternative routes in paths and have better fault-tolerance. Such loop networks, known as distributed loops have potential applications in local area networks, parallel processing and multicomputer interconnection environment. The shortest path between any two nodes in a distributed loop network has been studied for specific hop sizes. Results exist for computing this in O(delta) time, where delta is the diameter of the distributed loop. But there exists no closed form for the diameter. In this paper we consider distributed loops of n nodes having hop connections and without any knowledge of diameter, obtain the shortest path in O(h/g + log(h)) time, where h is the hop size and g is GCD(n, h). (C) 1998 Published by Elsevier Science B.V. All rights reserved. |
Year | DOI | Venue |
---|---|---|
1998 | 10.1016/S0020-0190(98)00099-4 | Inf. Process. Lett. |
Keywords | Field | DocType |
shortest path,loop network,fault tolerant,distributed system,modular arithmetic,parallel processing,distributed systems,local area network | Discrete mathematics,Shortest path problem,Modular arithmetic,Computer science,Parallel processing,Local area network,Hop (networking),Interconnection | Journal |
Volume | Issue | ISSN |
67 | 3 | 0020-0190 |
Citations | PageRank | References |
17 | 0.90 | 6 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Nimmagadda Chalamaiah | 1 | 19 | 2.43 |
Badrinath Ramamurthy | 2 | 23 | 4.19 |