A trade-off between space and efficiency for routing tables
From MaRDI portal
Publication:4710684
DOI10.1145/65950.65953zbMath0900.68262OpenAlexW2091569826MaRDI QIDQ4710684
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
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Stochastic network models in operations research (90B15) Deterministic scheduling theory in operations research (90B35)
Related Items (70)
Euclidean Steiner Spanners: Light and Sparse ⋮ Tree-decompositions with bags of small diameter ⋮ Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models ⋮ Bounding the locality of distributed routing algorithms ⋮ A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs ⋮ Proof labeling schemes ⋮ Spanners for bounded tree-length graphs ⋮ Routing among convex polygonal obstacles in the plane ⋮ Minimum \(t\)-spanners on subcubic graphs ⋮ Restrictions of minimum spanner problems ⋮ Covering metric spaces by few trees ⋮ Routing in polygonal domains ⋮ Average stretch analysis of compact routing schemes ⋮ On additive spanners in weighted graphs with local error ⋮ General variable neighborhood search for the minimum stretch spanning tree problem ⋮ Multi-dimensional Interval Routing Schemes ⋮ Improved weighted additive spanners ⋮ Distributed distance computation and routing with small messages ⋮ Space lower bounds for low-stretch greedy embeddings ⋮ Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs ⋮ Tree spanners of bounded degree graphs ⋮ Interval routing in some planar networks. ⋮ Approximation of minimum weight spanners for sparse graphs ⋮ Online Spanners in Metric Spaces ⋮ The sparsest additive spanner via multiple weighted BFS trees ⋮ Unnamed Item ⋮ Distributed computing of efficient routing schemes in generalized chordal graphs ⋮ Distance estimation and object location via rings of neighbors ⋮ Interval Routing Schemes for Circular-Arc Graphs ⋮ On the efficiency of routing in sensor networks ⋮ Turbo-Charging Dominating Set with an FPT Subroutine: Further Improvements and Experimental Analysis ⋮ Universal routing schemes ⋮ Interval routing schemes allow broadcasting with linear message-complexity ⋮ Compact and localized distributed data structures ⋮ Spanners in sparse graphs ⋮ Fast deterministic distributed algorithms for sparse spanners ⋮ On efficient distributed construction of near optimal routing schemes ⋮ Routing in unit disk graphs ⋮ Improved Approximation for the Directed Spanner Problem ⋮ Fault-Tolerant Compact Routing Schemes for General Graphs ⋮ Compact Routing in Unit Disk Graphs ⋮ A linear time algorithm to construct a tree 4-spanner on trapezoid graphs ⋮ Sparse covers for planar graphs and graphs that exclude a fixed minor ⋮ \(f\)-sensitivity distance oracles and routing schemes ⋮ Representing graphs implicitly using almost optimal space ⋮ Interval routing in reliability networks ⋮ Transitive-Closure Spanners: A Survey ⋮ Interval routing schemes ⋮ Distributed construction of purely additive spanners ⋮ NP-hardness and fixed-parameter tractability of the minimum spanner problem ⋮ Close to linear space routing schemes ⋮ The Greedy Spanner Is Existentially Optimal ⋮ Distributed algorithms for ultrasparse spanners and linear size skeletons ⋮ A note on distance-preserving graph sparsification ⋮ Covering Metric Spaces by Few Trees ⋮ The Sparsest Additive Spanner via Multiple Weighted BFS Trees ⋮ Multidimensional interval routing schemes ⋮ The compactness of adaptive routing tables ⋮ A distributed algorithm to find \(k\)-dominating sets ⋮ Distributed Computing of Efficient Routing Schemes in Generalized Chordal Graphs ⋮ The complexity of shortest path and dilation bounded interval routing ⋮ A survey on interval routing ⋮ Distributed Spanner Approximation ⋮ Computing (and Life) Is All about Tradeoffs ⋮ Light spanners for high dimensional norms via stochastic decompositions ⋮ The complexity of the characterization of networks supporting shortest-path interval routing. ⋮ Fault tolerant additive and \((\mu, \alpha)\)-spanners ⋮ Routing in Polygonal Domains ⋮ Static and dynamic low-congested interval routing schemes ⋮ Graph theoretical issues in computer networks
This page was built for publication: A trade-off between space and efficiency for routing tables
