Efficient Message Routing in Planar Networks
Authors:
- 1 August 1989
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 18 (4) , 843-857
Abstract
The problem of routing messages along near-shortest paths in a distributed network without using complete routing tables is considered. It is assumed that the nodes of the network can be assigned suitable short names at the time the network is established. Two space-efficient near-shortest-path routing schemes are given for the class of planar networks. Both schemes use the separator property of planar networks in assigning the node names and performing the routings. For an n-node network, the first scheme uses $O(\log n)$-bit names and a total of $O(n^{{4 / 3}} )$ items of routing information, each $O(\log n)$ bits long, to generate routings that are only three times longer than corresponding shortest routings in worst cases. For any constant $\epsilon ,0 < \epsilon < 1/3$, the second scheme achieves the better space bound of $O(n^{1 + \epsilon } )$ items, each $O(({1 / \epsilon })\log n)$ bits long, but at the expense of $O(({1 / \epsilon })\log n)$-bit node names and a worst-case bound of 7 on the routings.
Keywords
This publication has 14 references indexed in Scilit:
- Space-Efficient Message Routing inc-Decomposable NetworksSIAM Journal on Computing, 1990
- Designing networks with compact routing tablesAlgorithmica, 1988
- Fast Algorithms for Shortest Paths in Planar Graphs, with ApplicationsSIAM Journal on Computing, 1987
- Finding small simple cycle separators for 2-connected planar graphsJournal of Computer and System Sciences, 1986
- Labelling and Implicit Routing in NetworksThe Computer Journal, 1985
- A Separator Theorem for Planar GraphsSIAM Journal on Applied Mathematics, 1979
- Hierarchical routing for large networks Performance evaluation and optimizationComputer Networks (1976), 1977
- Graph Theory with Applications1976
- GRAPH THEORY1969
- Topology of series-parallel networksJournal of Mathematical Analysis and Applications, 1965