Classes of network topologies are identified in which shortest paths information can be succinctly stored at the nodes, if suitable names are assigned to them. The naming allows each edge at a node to be labelled with zero or more intervals of integers, representing all nodes reachable by a shortest path via that edge. Starting with the class of outerplanar networks, a natural hierarchy is established, based on the number of intervals required. The outerplanar networks are shown to be precisely the networks requiring just one interval per edge. An optimal algorithm is given for determining the labels for edges in outerplanar networks.
|Original language||English (US)|
|Title of host publication||Proceedings of the Annual ACM Symposium on Principles of Distributed Computing|
|Publisher||Association for Computing Machinery|
|Number of pages||10|
|State||Published - Nov 1 1986|
|Event||5th Annual ACM Symposium on Principles of Distributed Computing, PODC 1986 - Calgary, Canada|
Duration: Aug 11 1986 → Aug 13 1986
|Name||Proceedings of the Annual ACM Symposium on Principles of Distributed Computing|
|Other||5th Annual ACM Symposium on Principles of Distributed Computing, PODC 1986|
|Period||8/11/86 → 8/13/86|
Bibliographical noteFunding Information:
1. Introduction A basic activity in a distributed network is the routing of messages between pairs of nodes. Assuming a cost function on the edges of the network, it is desirable that the routing of each message be along a shortest path. A straightforward approach is to maintain a complete routing table at each of the n nodes, which gives for each potential destination the name of the next node on a shortest path to the destination. This approach * This research was supported in part by the National Science Foundation under grant DCR-8320124.
© 1986 ACM.