SEPARATOR-BASED STRATEGIES FOR EFFICIENT MESSAGE ROUTING.

Message routing strategies are given for networks with certain separator properties. These strategies use considerably less space than complete routing tables, keep node names to O(log n) bits, and still route along near-shortest paths. For any network with separators of size at most a small constant c, a total of O(n log n) items of routing information is stored, and any message is routed along a path of length at most (2/ alpha ) plus 1 times the length of an optimal path, where alpha greater than 1 is the positive root of the equation alpha left bracket **(**c** plus **1**)**/**2 right bracket minus alpha minus 2 equals 0. For planar networks, O(n**1** plus epsilon ) items are stored, for any constant epsilon , 0 less than epsilon less than 1/3, and the length of any message path is at most 7 times that of an optimal path.