On approximate distance labels and routing schemes with affine stretch
From MaRDI portal
Publication:3095345
DOI10.1007/978-3-642-24100-0_39zbMATH Open1350.68020OpenAlexW1900076025MaRDI QIDQ3095345FDOQ3095345
Authors: Ittai Abraham, Cyril Gavoille 
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
Recommendations
Graph theory (including graph drawing) in computer science (68R10) Network design and communication in computer systems (68M10) Network protocols (68M12)
Cites Work
- Approximate distance oracles
- Computing almost shortest paths
- On sparse spanners of weighted graphs
- Ramsey partitions and proximity data structures
- Additive spanners and \(({\alpha}, {\beta})\)-spanners
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Distance Oracles for Sparse Graphs
- Distance oracles beyond the Thorup-Zwick bound
- Title not available (Why is that?)
- Stochastic performance evaluation of hierarchical routing for large networks
- Compact name-independent routing with minimum stretch
- Low Distortion Spanners
- $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
- Spanners and emulators with sublinear distance errors
Cited In (only showing first 100 items - show all)
- On the Lovász theta function for independent sets in sparse graphs
- Matching triangles and basing hardness on an extremely popular conjecture
- Efficiently learning Ising models on arbitrary graphs (extended abstract)
- Sparse quantum codes from quantum circuits
- Routing among convex polygonal obstacles in the plane
- Routing in polygonal domains
- Routing in polygonal domains
- Beyond the Euler characteristic: approximating the genus of general graphs (extended abstract)
- Spectral sparsification and regret minimization beyond matrix multiplicative updates
- Compact Routing in Unit Disk Graphs
- Preserving statistical validity in adaptive data analysis (extended abstract)
- A polynomial-time bicriteria approximation scheme for planar bisection
- Random permutations using switching networks
- Randomized composable core-sets for distributed submodular maximization
- Polynomially low error PCPs with \(\operatorname{polyloglog} n\) queries via modular composition
- The Power of Dynamic Distance Oracles
- Almost Optimal Pseudorandom Generators for Spherical Caps
- Dictionary learning and tensor decomposition via the sum-of-squares method
- Small value parallel repetition for general games
- \(\ell_p\) row sampling by Lewis weights
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Nearly-linear time positive LP solver with faster convergence rate
- Inapproximability of Nash equilibrium
- Sketching and embedding are equivalent for norms
- Minimizing flow-time on unrelated machines
- Close to linear space routing schemes
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
- From independence to expansion and back again
- Test-and-set in optimal space
- Dimensionality reduction for \(k\)-means clustering and low rank approximation
- Adjacency labeling schemes and induced-universal graphs
- Non-malleable reductions and applications
- Learning mixtures of Gaussians in high dimensions
- Approximate \(k\)-flat nearest neighbor search
- Optimal data-dependent hashing for approximate near neighbors
- Randomized rounding for the largest simplex problem
- Approximate distance oracles with improved bounds
- The directed grid theorem
- Testing cluster structure of graphs
- Byzantine agreement with optimal early stopping, optimal resilience and polynomial complexity
- Succinct randomized encodings and their applications
- Reed-Muller codes for random erasures and errors
- On the complexity of Nash equilibria in anonymous games
- Indistinguishability obfuscation for Turing machines with unbounded memory
- Succinct garbling and indistinguishability obfuscation for RAM programs
- Garbled RAM from one-way functions
- Quantum information complexity
- Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions
- A hierarchy of lower bounds for sublinear additive spanners
- 2-server PIR with sub-polynomial communication
- Computing with Tangles
- Secretary Problems with Non-Uniform Arrival Order
- Forrelation: a problem that optimally separates quantum from classical computing
- Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
- Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
- An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
- FPTAS for \#BIS with degree bounds on one side
- Deterministic global minimum cut of a simple graph in near-linear time
- Leveled fully homomorphic signatures from standard lattices
- How well can graphs represent wireless interference?
- The complexity of the simplex method
- Super-resolution, extremal functions and the condition number of Vandermonde matrices
- Online submodular welfare maximization: greedy beats 1/2 in random order
- Hardness of Graph Pricing Through Generalized Max-Dicut
- Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
- Shortest-path queries in static networks
- Local, private, efficient protocols for succinct histograms
- Quantum spectrum testing
- High Parallel Complexity Graphs and Memory-Hard Functions
- Greedy algorithms for Steiner forest
- Fast matrix multiplication: limitations of the Coppersmith-Winograd method (extended abstract)
- Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension
- Bypassing KLS: Gaussian cooling and an \(O^\ast(n^3)\) volume algorithm
- Faster canonical forms for primitive coherent configurations (extended abstract)
- Solving the shortest vector problem in \(2^n\) time using discrete Gaussian sampling (extended abstract)
- Excluded grid theorem: improved and simplified
- Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries
- Learning Arbitrary Statistical Mixtures of Discrete Distributions
- Tight bounds for learning a mixture of two Gaussians (extended abstract)
- Exponential Separation of Information and Communication for Boolean Functions
- Rectangles Are Nonnegative Juntas
- Toward a unified theory of sparse dimensionality reduction in Euclidean space
- Approximating Nash equilibria and dense bipartite subgraphs via an approximate version of Carathéodory's theorem
- Approximating the Nash social welfare with indivisible items
- Prioritized metric structures and embedding
- Proof of the satisfiability conjecture for large \(k\)
- Reachability and Distance Queries via 2-Hop Labels
- On the complexity of random satisfiability problems with planted solutions (extended abstract)
- Sum of squares lower bounds from pairwise independence (extended abstract)
- Clustered Integer 3SUM via Additive Combinatorics
- Consistency thresholds for the planted bisection model
- Inapproximability of combinatorial problems via small LPs and SDPs
- An interactive information odometer and applications
- Lower bounds on the size of semidefinite programming relaxations
- Sum-of-squares Lower Bounds for Planted Clique
- Approximate distance sensitivity oracles in subquadratic space
- A characterization of the capacity of online (causal) binary channels
- Time lower bounds for nonadaptive turnstile streaming algorithms
- Analysis of a classical matrix preconditioning algorithm
- Distance queries over dynamic interval graphs
This page was built for publication: On approximate distance labels and routing schemes with affine stretch
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3095345)
