A trade-off between space and efficiency for routing tables

DOI10.1145/65950.65953zbMath0900.68262MaRDI QIDQ4710684

David Peleg, Eli Upfal

Publication date: 25 June 1992

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/65950.65953

zbMATH Keywords

random graphs; lower bound; routing schemes; hierarchical routing; stretch factor; routing tables

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

90B15: Stochastic network models in operations research

90B35: Deterministic scheduling theory in operations research

Related Items

Transitive-Closure Spanners: A Survey, A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs, Representing graphs implicitly using almost optimal space, Interval routing schemes, Approximation of minimum weight spanners for sparse graphs, Average stretch analysis of compact routing schemes, Fast deterministic distributed algorithms for sparse spanners, Multidimensional interval routing schemes, Graph theoretical issues in computer networks, Restrictions of minimum spanner problems, Interval routing in some planar networks., The complexity of shortest path and dilation bounded interval routing, A survey on interval routing, Static and dynamic low-congested interval routing schemes, Interval routing in reliability networks, The compactness of adaptive routing tables, A distributed algorithm to find \(k\)-dominating sets, The complexity of the characterization of networks supporting shortest-path interval routing., Tree-decompositions with bags of small diameter, Spanners for bounded tree-length graphs, Distributed Computing of Efficient Routing Schemes in Generalized Chordal Graphs, A linear time algorithm to construct a tree 4-spanner on trapezoid graphs