A trade-off between space and efficiency for routing tables

No abstract is available for this paper.

• Publication year

  1989

• Venue

  JACM

• Publication date

  1989-07-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/65950.65953
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Improved Routing Strategies with Succinct Tables

  1990cited by this paper
• Compact distributed data structures for adaptive routing

  1989cited by this paper
• Graph spanners

  1989cited by this paper
• Interval Routing

  1987cited by this paper
• An optimal synchronizer for the hypercube

  1987cited by this paper
• Separator-based strategies for efficient message routing

  1986cited by this paper
• Establishing Virtual Circuits in Large Computer Networks

  1986cited by this paper
• Complexity of network synchronization

  1985cited by this paper
• An upper bound for the k-domination number of a graph

  1985cited by this paper
• Hierarchical Networks and the Subnetwork Partition Problem

  1985cited by this paper
• Random Graphs

  1985cited by this paper
• Labelling and Implicit Routing in Networks

  1985cited by this paper
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs

  1984cited by this paper
• Routing with compact routing tables

  1983cited by this paper
• Optimal clustering structures for hierarchical topological design of large computer networks

  1980cited by this paper
• Hierarchical Routing for Large Networks; Performance Evaluation and Optimization

  1977cited by this paper
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

  1952cited by this paper

• Practical parallel algorithms for compact spanners on real world graphs

  2026cites this paper
• Compact routing schemes in undirected and directed graphs

  2025cites this paper
• Sublinear Edge Fault Tolerant Spanners for Hypergraphs

  2025cites this paper
• How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs

  2025cites this paper
• Carousel greedy algorithms for the minimum stretch spanning tree problem

  2025cites this paper
• A Unified Framework of Light Spanners I: Fast (Yet Optimal) Constructions

  2025cites this paper
• Light Edge Fault Tolerant Graph Spanners

  2025cites this paper
• Stronger Directed Low-Diameter Decompositions with Sub-Logarithmic Diameter and Separation

  2025cites this paper
• Bounded Memory in Distributed Networks

  2025cites this paper
• A divide-and-conquer based preprocessing for routing in a simple polygon

  2025cites this paper
• Local Routing on a Convex Polytope in R^3

  2025cites this paper
• New weighted additive spanners

  2024cites this paper
• On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and other applications

  2024cites this paper
• An artificial bee colony algorithm for the minimum edge-dilation K-center problem

  2024cites this paper
• Sparse Spanners with Small Distance and Congestion Stretches

  2024cites this paper
• Parks and Recreation: Color Fault-Tolerant Spanners Made Local

  2024cites this paper
• Polynomial algorithms for sparse spanners on subcubic graphs

  2024cites this paper
• An Iterated Local Search for the Minimum Edge-Dilation K-Center Problem

  2023cites this paper
• Spanning Adjacency Oracles in Sublinear Time

  2023cites this paper
• Are there graphs whose shortest path structure requires large edge weights?

  2023cites this paper
• An Alternate Proof of Near-Optimal Light Spanners

  2023cites this paper
• Scalable algorithms for compact spanners on real world graphs

  2023cites this paper
• Space-Stretch Tradeoff in Routing Revisited

  2022cites this paper
• Euclidean Steiner Spanners: Light and Sparse

  2022cites this paper
• Online Spanners in Metric Spaces

  2022cites this paper
• Routing Schemes and Distance Oracles in the Hybrid Model

  2022cites this paper
• Õptimal Vertex Fault-Tolerant Spanners in Õptimal Time: Sequential, Distributed and Parallel

  2022cites this paper
• General variable neighborhood search for the minimum stretch spanning tree problem

  2022cites this paper
• New Additive Spanner Lower Bounds by an Unlayered Obstacle Product

  2022influential citation
• Bridge Girth: A Unifying Notion in Network Design

  2022cites this paper
• Nearly optimal vertex fault-tolerant spanners in optimal time: sequential, distributed, and parallel

  2022cites this paper
• Constant-Round Spanners and Shortest Paths in Congested Clique and MPC

  2021cites this paper
• Spanner Approximations in Practice

  2021cites this paper
• Can't See the Forest for the Trees: Navigating Metric Spaces by Bounded Hop-Diameter Spanners

  2021cites this paper
• Hop-Constrained Metric Embeddings and their Applications

  2021cites this paper
• A Unified Framework for Hopsets and Spanners

  2021cites this paper
• Near-Optimal Spanners for General Graphs in (Nearly) Linear Time

  2021cites this paper
• A Unified Framework of Light Spanners II: Fine-Grained Optimality

  2021cites this paper
• Partially Optimal Edge Fault-Tolerant Spanners

  2021cites this paper
• Improved Local Computation Algorithms for Constructing Spanners

  2021cites this paper
• A Multicast Routing Scheme for the Internet: Simulation and Experimentation in Large-Scale Networks

  2021cites this paper
• Improved LCAs for constructing spanners

  2021cites this paper
• Routing Among Convex Polygonal Obstacles in the Plane

  2021cites this paper
• Towards a Unified Theory of Light Spanners I: Fast (Yet Optimal) Constructions

  2021cites this paper
• Reliable Spanners: Locality-Sensitive Orderings Strike Back

  2021cites this paper
• Weighted Sparse and Lightweight Spanners with Local Additive Error

  2021cites this paper
• Strongly Hyperbolic Unit Disk Graphs

  2021cites this paper
• An Improved Random Shift Algorithm for Spanners and Low Diameter Decompositions

  2021cites this paper
• Clan embeddings into trees, and low treewidth graphs

  2021cites this paper
• On Additive Spanners in Weighted Graphs with Local Error

  2021cites this paper
• Optimal Vertex Fault-Tolerant Spanners in Polynomial Time

  2020cites this paper
• Improved weighted additive spanners

  2020cites this paper
• A Unified and Fine-Grained Approach for Light Spanners

  2020cites this paper
• Headerless Routing in Unit Disk Graphs ∗

  2020cites this paper
• Extremal Distances in Directed Graphs: Tight Spanners and Near-Optimal Approximation Algorithms

  2020cites this paper
• On the Edge Crossings of the Greedy Spanner

  2020cites this paper
• Weighted Additive Spanners

  2020cites this paper
• WALCOM: Algorithms and Computation: 14th International Conference, WALCOM 2020, Singapore, Singapore, March 31 – April 2, 2020, Proceedings

  2020cites this paper
• Semi-Exact Exponential-Time Algorithms: an Experimental Study

  2020cites this paper
• Implementing and Evaluating sparsification methods in probabilistic networks

  2020cites this paper
• Light Euclidean Steiner Spanners in the Plane

  2020cites this paper
• Distributed Network Design

  2020cites this paper
• A note on distance-preserving graph sparsification

  2020influential citation
• Routing in Unit Disk Graphs without Dynamic Headers

  2020cites this paper
• On Euclidean Steiner (1+ε)-Spanners

  2020cites this paper
• Compact Routing in Unit Disk Graphs

  2020cites this paper
• Efficient network navigation with partial information

  2020cites this paper
• An FPT Algorithm for Minimum Additive Spanner Problem

  2019cites this paper
• Distributed distance computation and routing with small messages

  2019cites this paper
• Near-Additive Spanners In Low Polynomial Deterministic CONGEST Time

  2019cites this paper
• Message Reduction in the LOCAL Model is a Free Lunch

  2019cites this paper
• Covering Metric Spaces by Few Trees

  2019cites this paper
• Routing in Histograms

  2019cites this paper
• Diameter Spanner, Eccentricity Spanner, and Approximating Extremal Graph Distances: Static, Dynamic, and Fault Tolerant

  2018cites this paper
• NP-hardness and fixed-parameter tractability of the minimum spanner problem

  2018cites this paper
• Distributed Spanner Approximation

  2018cites this paper
• The Sparsest Additive Spanner via Multiple Weighted BFS Trees

  2018cites this paper
• Diameter Spanners, Eccentricity Spanners, and Approximating Extremal Distances

  2018cites this paper
• A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners

  2018cites this paper
• Near-Optimal Distributed Routing with Low Memory

  2018cites this paper
• Sublinear Graph Augmentation for Fast Query Implementation

  2018cites this paper
• 7 : 2 The Sparsest Additive Spanner via Multiple Weighted BFS Trees 1

  2018cites this paper
• Light Spanners for High Dimensional Norms via Stochastic Decompositions

  2018cites this paper
• Routing in Polygonal Domains

  2017cites this paper
• Optimal Vertex Fault Tolerant Spanners (for fixed stretch)

  2017cites this paper
• Linear-Size Hopsets with Small Hopbound, and Distributed Routing with Low Memory

  2017cites this paper
• Routing in Polygons with Holes

  2017cites this paper
• Scale the Internet routing table by generalized next hops of strict partial order

  2017cites this paper
• Distance Computation and Routing with Small Messages

  2017cites this paper
• Routing in Simple Polygons

  2017cites this paper
• Turbo-Charging Dominating Set with an FPT Subroutine: Further Improvements and Experimental Analysis

  2017cites this paper
• Solving the minimum edge-dilation k-center problem by genetic algorithms

  2017cites this paper
• Distributed Domination on Graph Classes of Bounded Expansion

  2017cites this paper
• Trap Array: A Unified Model for Scalability Evaluation of Geometric Routing

  2016cites this paper
• The Greedy Spanner is Existentially Optimal

  2016cites this paper
• Deterministic decremental single source shortest paths: beyond the o(mn) bound

  2016cites this paper
• Near-Optimal Light Spanners

  2016cites this paper
• Disk Intersection Graphs: Models, Data Structures, and Algorithms

  2016cites this paper
• Sparse Fault-Tolerant BFS Structures

  2016cites this paper
• Simple Algorithms for Spanners in Weighted Graphs

  2016cites this paper