On Approximate Distance Labels and Routing Schemes with Affine Stretch
From MaRDI portal
Publication:3095345
DOI10.1007/978-3-642-24100-0_39zbMath1350.68020OpenAlexW1900076025MaRDI QIDQ3095345
Publication date: 28 October 2011
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-24100-0_39
Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Network protocols (68M12)
Related Items (only showing first 100 items - show all)
Approximate distance oracles with improved stretch for sparse graphs ⋮ Compact Routing in Unit Disk Graphs ⋮ Close to linear space routing schemes ⋮ Approximate distance oracles with improved stretch for sparse graphs ⋮ Consistency thresholds for the planted bisection model ⋮ Routing among convex polygonal obstacles in the plane ⋮ A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ Routing in polygonal domains ⋮ Approximate Distance Oracles with Improved Bounds ⋮ The Power of Dynamic Distance Oracles ⋮ Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture ⋮ Clustered Integer 3SUM via Additive Combinatorics ⋮ Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false) ⋮ Proof of the Satisfiability Conjecture for Large k ⋮ On the Complexity of Random Satisfiability Problems with Planted Solutions ⋮ Sum-of-squares Lower Bounds for Planted Clique ⋮ Sum of Squares Lower Bounds from Pairwise Independence ⋮ Inapproximability of Combinatorial Problems via Small LPs and SDPs ⋮ Preserving Statistical Validity in Adaptive Data Analysis ⋮ Local, Private, Efficient Protocols for Succinct Histograms ⋮ Improved Noisy Population Recovery, and Reverse Bonami-Beckner Inequality for Sparse Functions ⋮ Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method ⋮ Randomized Composable Core-sets for Distributed Submodular Maximization ⋮ Dimensionality Reduction for k-Means Clustering and Low Rank Approximation ⋮ Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams ⋮ L p Row Sampling by Lewis Weights ⋮ On the Lovász Theta function for Independent Sets in Sparse Graphs ⋮ The Complexity of the Simplex Method ⋮ An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm ⋮ Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs ⋮ Nearly-Linear Time Positive LP Solver with Faster Convergence Rate ⋮ Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates ⋮ Almost Optimal Pseudorandom Generators for Spherical Caps ⋮ Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition ⋮ The List Decoding Radius of Reed-Muller Codes over Small Fields ⋮ A Characterization of the Capacity of Online (causal) Binary Channels ⋮ Reed-Muller Codes for Random Erasures and Errors ⋮ Forrelation ⋮ Quantum Information Complexity ⋮ Sparse Quantum Codes from Quantum Circuits ⋮ Small Value Parallel Repetition for General Games ⋮ An Interactive Information Odometer and Applications ⋮ The communication complexity of interleaved group products ⋮ Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem ⋮ Approximating the Nash Social Welfare with Indivisible Items ⋮ On the Complexity of Nash Equilibria in Anonymous Games ⋮ Hardness of Graph Pricing Through Generalized Max-Dicut ⋮ Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension ⋮ Inapproximability of Nash Equilibrium ⋮ Indistinguishability Obfuscation for Turing Machines with Unbounded Memory ⋮ Succinct Garbling and Indistinguishability Obfuscation for RAM Programs ⋮ Succinct Randomized Encodings and their Applications ⋮ Garbled RAM From One-Way Functions ⋮ Non-malleable Reductions and Applications ⋮ Leveled Fully Homomorphic Signatures from Standard Lattices ⋮ Sketching and Embedding are Equivalent for Norms ⋮ Prioritized Metric Structures and Embedding ⋮ A Directed Isoperimetric Inequality with application to Bregman Near Neighbor Lower Bounds ⋮ Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries ⋮ Bypassing KLS ⋮ FPTAS for #BIS with Degree Bounds on One Side ⋮ Lower Bounds on the Size of Semidefinite Programming Relaxations ⋮ 2-Server PIR with Sub-Polynomial Communication ⋮ Fast Matrix Multiplication ⋮ High Parallel Complexity Graphs and Memory-Hard Functions ⋮ Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity ⋮ Test-and-Set in Optimal Space ⋮ Adjacency Labeling Schemes and Induced-Universal Graphs ⋮ How Well Can Graphs Represent Wireless Interference? ⋮ Excluded Grid Theorem ⋮ The Directed Grid Theorem ⋮ Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time ⋮ Beyond the Euler Characteristic ⋮ Faster Canonical Forms for Primitive Coherent Configurations ⋮ Random Permutations using Switching Networks ⋮ Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms ⋮ Testing Cluster Structure of Graphs ⋮ Solving the Shortest Vector Problem in 2 n Time Using Discrete Gaussian Sampling ⋮ Learning Arbitrary Statistical Mixtures of Discrete Distributions ⋮ Tight Bounds for Learning a Mixture of Two Gaussians ⋮ Learning Mixtures of Gaussians in High Dimensions ⋮ Efficiently Learning Ising Models on Arbitrary Graphs ⋮ Approximate k -flat Nearest Neighbor Search ⋮ Optimal Data-Dependent Hashing for Approximate Near Neighbors ⋮ Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms ⋮ From Independence to Expansion and Back Again ⋮ Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices ⋮ Analysis of a Classical Matrix Preconditioning Algorithm ⋮ A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection ⋮ Minimizing Flow-Time on Unrelated Machines ⋮ Randomized Rounding for the Largest Simplex Problem ⋮ Greedy Algorithms for Steiner Forest ⋮ Secretary Problems with Non-Uniform Arrival Order ⋮ Online Submodular Welfare Maximization ⋮ Quantum spectrum testing ⋮ Toward a unified theory of sparse dimensionality reduction in Euclidean space ⋮ Shortest-path queries in static networks ⋮ Computing with Tangles ⋮ Rectangles Are Nonnegative Juntas
Cites Work
- Unnamed Item
- Ramsey partitions and proximity data structures
- On sparse spanners of weighted graphs
- Additive spanners and (α, β)-spanners
- Approximate distance oracles
- Spanners and emulators with sublinear distance errors
- Stochastic performance evaluation of hierarchical routing for large networks
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
- Compact name-independent routing with minimum stretch
- Distance Oracles for Sparse Graphs
- Distance Oracles beyond the Thorup--Zwick Bound
- Low Distortion Spanners
- Computing almost shortest paths
This page was built for publication: On Approximate Distance Labels and Routing Schemes with Affine Stretch