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
Publisher Copyright:© 1986 ACM.