TY - GEN

T1 - SEPARATOR-BASED STRATEGIES FOR EFFICIENT MESSAGE ROUTING.

AU - Frederickson, Greg N.

AU - Janardan, Ravi

PY - 1986

Y1 - 1986

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0022877554&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0022877554&partnerID=8YFLogxK

U2 - 10.1109/sfcs.1986.49

DO - 10.1109/sfcs.1986.49

M3 - Conference contribution

AN - SCOPUS:0022877554

SN - 0818607408

SN - 9780818607400

T3 - Annual Symposium on Foundations of Computer Science (Proceedings)

SP - 428

EP - 437

BT - Annual Symposium on Foundations of Computer Science (Proceedings)

PB - IEEE

ER -