Abstract
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 |
Pages | 88-97 |
Number of pages | 10 |
ISBN (Electronic) | 0897911989 |
DOIs | |
State | Published - Nov 1 1986 |
Externally published | Yes |
Event | 5th Annual ACM Symposium on Principles of Distributed Computing, PODC 1986 - Calgary, Canada Duration: Aug 11 1986 → Aug 13 1986 |
Publication series
Name | Proceedings of the Annual ACM Symposium on Principles of Distributed Computing |
---|
Other
Other | 5th Annual ACM Symposium on Principles of Distributed Computing, PODC 1986 |
---|---|
Country/Territory | Canada |
City | Calgary |
Period | 8/11/86 → 8/13/86 |
Bibliographical note
Funding 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.
Publisher Copyright:
© 1986 ACM.