Approximate distance oracles
From MaRDI portal
Publication:3546311
DOI10.1145/1044731.1044732zbMath1175.68303OpenAlexW2045446569MaRDI QIDQ3546311
Publication date: 21 December 2008
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1044731.1044732
Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Data structures (68P05)
Related Items
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Small Stretch Pairwise Spanners and Approximate $D$-Preservers ⋮ A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs ⋮ Path-Fault-Tolerant Approximate Shortest-Path Trees ⋮ Coloring and Covering Nowhere Dense Graphs ⋮ A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ Adjacency Labeling Schemes and Induced-Universal Graphs ⋮ Optimal (Euclidean) Metric Compression ⋮ Lossless Prioritized Embeddings ⋮ 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 ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Online, Dynamic, and Distributed Embeddings of Approximate Ultrametrics ⋮ Advances in metric embedding theory ⋮ Steiner Point Removal with Distortion $O(\log {k})$ using the Relaxed-Voronoi Algorithm ⋮ Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ Improved Approximation for the Directed Spanner Problem ⋮ Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs ⋮ VC-Dimension and Shortest Path Algorithms ⋮ Fault-Tolerant Compact Routing Schemes for General Graphs ⋮ Distance Oracles for Vertex-Labeled Graphs ⋮ The idemetric property: when most distances are (almost) the same ⋮ Multipath Spanners via Fault-Tolerant Spanners ⋮ Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners ⋮ Shortest-path queries in static networks ⋮ Transitive-Closure Spanners: A Survey ⋮ A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs ⋮ Distributed construction of purely additive spanners ⋮ Unnamed Item ⋮ Approximating Shortest Paths in Graphs ⋮ Close to linear space routing schemes ⋮ Computing with Tangles ⋮ Rectangles Are Nonnegative Juntas ⋮ Improved Guarantees for Vertex Sparsification in Planar Graphs ⋮ Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs ⋮ Exponential Separation of Information and Communication for Boolean Functions ⋮ Unnamed Item ⋮ Constructing Light Spanners Deterministically in Near-Linear Time ⋮ Distributed algorithms for ultrasparse spanners and linear size skeletons ⋮ On Approximate Distance Labels and Routing Schemes with Affine Stretch ⋮ Approximate distance oracles with improved stretch for sparse graphs ⋮ Unnamed Item ⋮ Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs ⋮ Faster algorithms for shortest path and network flow based on graph decomposition ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Distributed Spanner Approximation ⋮ Cutting Corners Cheaply, or How to Remove Steiner Points ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time ⋮ Routing in Polygonal Domains ⋮ Consistency thresholds for the planted bisection model ⋮ Distance oracles for time-dependent networks ⋮ Thorup-Zwick emulators are universally optimal hopsets ⋮ Byzantine gathering in polynomial time ⋮ Routing among convex polygonal obstacles in the plane ⋮ Succinct posets ⋮ Minimum \(t\)-spanners on subcubic graphs ⋮ On random perfect matchings in metric spaces with not-too-large diameters ⋮ 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 ⋮ Deterministic improved round-trip spanners ⋮ Strong-diameter decompositions of minor free graphs ⋮ Near-optimal induced universal graphs for cycles and paths ⋮ Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem ⋮ An introduction to the Ribe program ⋮ Distributed distance computation and routing with small messages ⋮ Fast rendezvous with advice ⋮ Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs ⋮ New pairwise spanners ⋮ Approximation of minimum weight spanners for sparse graphs ⋮ Additive spanners and distance and routing labeling schemes for hyperbolic graphs ⋮ Faster algorithms for all-pairs small stretch distances in weighted graphs ⋮ New approximation algorithms for minimum cycle bases of graphs ⋮ Drawing maps with advice ⋮ Ultrametric subsets with large Hausdorff dimension ⋮ Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs ⋮ On dynamic shortest paths problems ⋮ Distance estimation and object location via rings of neighbors ⋮ Compact navigation and distance oracles for graphs with small treewidth ⋮ Spanners in sparse graphs ⋮ Fast deterministic distributed algorithms for sparse spanners ⋮ Quantum spectrum testing ⋮ Toward a unified theory of sparse dimensionality reduction in Euclidean space ⋮ On efficient distributed construction of near optimal routing schemes ⋮ Efficient vertex-label distance oracles for planar graphs ⋮ Space-efficient path-reporting approximate distance oracles ⋮ Impact of knowledge on election time in anonymous networks ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ \(f\)-sensitivity distance oracles and routing schemes ⋮ Trade-offs between the size of advice and broadcasting time in trees ⋮ Communication algorithms with advice ⋮ Approximate shortest paths guided by a small index ⋮ Electric routing and concurrent flow cutting ⋮ Preprocess, set, query! ⋮ NP-hardness and fixed-parameter tractability of the minimum spanner problem ⋮ A fast algorithm for source-wise round-trip spanners ⋮ All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time ⋮ Advice complexity of treasure hunt in geometric terrains ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs ⋮ Efficient distributed computation of distance sketches in networks ⋮ Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization ⋮ Localized and compact data-structure for comparability graphs ⋮ Colouring and Covering Nowhere Dense Graphs ⋮ Exact and approximation algorithms for weighted matroid intersection ⋮ Multiple-edge-fault-tolerant approximate shortest-path trees ⋮ Constructing light spanners deterministically in near-linear time ⋮ Decomposing a graph into shortest paths with bounded eccentricity ⋮ Light spanners for high dimensional norms via stochastic decompositions ⋮ Fault tolerant additive and \((\mu, \alpha)\)-spanners ⋮ Topology recognition with advice ⋮ An axiomatic approach to time-dependent shortest path oracles ⋮ Approximate distance oracles with improved stretch for sparse graphs ⋮ Communication-efficient distributed graph clustering and sparsification under duplication models ⋮ Four shades of deterministic leader election in anonymous networks ⋮ A novel pseudo‐polynomial approach for shortest path problems ⋮ Tree 3-spanners on generalized prisms of graphs ⋮ Labelings vs. embeddings: on distributed and prioritized representations of distances ⋮ Compact distance oracles with large sensitivity and low stretch ⋮ Unnamed Item ⋮ Shortest-Path Queries in Geometric Networks
