SEPARATOR-BASED STRATEGIES FOR EFFICIENT MESSAGE ROUTING.

Greg N. Frederickson, Ravi Janardan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

20 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherIEEE
Pages428-437
Number of pages10
ISBN (Print)0818607408, 9780818607400
DOIs
StatePublished - 1986

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

Fingerprint Dive into the research topics of 'SEPARATOR-BASED STRATEGIES FOR EFFICIENT MESSAGE ROUTING.'. Together they form a unique fingerprint.

Cite this