Light spanners for high dimensional norms via stochastic decompositions
From MaRDI portal
Publication:2088589
DOI10.1007/s00453-022-00994-0OpenAlexW2962701863MaRDI QIDQ2088589
Publication date: 6 October 2022
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-022-00994-0
treewidthspannersdoubling dimensiongenus graphshigh dimensional euclidean spacestochastic decompositions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Ramsey partitions and proximity data structures
- On sparse spanners of weighted graphs
- Low diameter graph decompositions
- Extending Lipschitz functions via random metric partitions
- A sparse graph almost as good as the complete graph on points in \(k\) dimensions
- The geometry of graphs and some of its algorithmic applications
- Graph spanners: a tutorial review
- Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
- Measured descent: A new embedding method for finite metrics
- A subset spanner for Planar graphs, with application to subset TSP
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Sparse Sourcewise and Pairwise Distance Preservers
- Geometric Spanner Networks
- Approximate distance oracles
- Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
- Bypassing the embedding
- The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension
- Complexity of network synchronization
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Distributed Computing: A Locality-Sensitive Approach
- Light graphs with small routing cost
- On the optimality of the random hyperplane rounding technique for MAX CUT
- Near-Optimal Light Spanners
- Ramsey Spanning Trees and Their Applications
- Approximation Algorithms for the 0-Extension Problem
- NEW SPARSENESS RESULTS ON GRAPH SPANNERS
- A trade-off between space and efficiency for routing tables
- An Optimal Synchronizer for the Hypercube
- Truly Optimal Euclidean Spanners
- Light Spanners
- Higher Eigenvalues of Graphs
- Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs
- Greedy spanners are optimal in doubling metrics
- Excluded minors, network decomposition, and multicommodity flow
- The Greedy Spanner is Existentially Optimal
- Algorithms – ESA 2004
- Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
- Automata, Languages and Programming
- Euclidean Spanners in High Dimensions
- Distributed Construction of Light Networks
- Computing almost shortest paths
- Advances in metric embedding theory
- A tight bound on approximating arbitrary metrics by tree metrics
- Clan embeddings into trees, and low treewidth graphs
This page was built for publication: Light spanners for high dimensional norms via stochastic decompositions
