scientific article; zbMATH DE number 7378699

DOI10.4230/LIPIcs.ESA.2018.29MaRDI QIDQ5009588

Ofer Neiman, Arnold Filtser

Publication date: 4 August 2021

Full work available at URL: https://arxiv.org/abs/1804.07456

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

spannersdoubling dimensiongenus graphsstochastic decompositionshigh dimensional Euclidean space

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (4)

Covering metric spaces by few trees ⋮ Unnamed Item ⋮ Light Euclidean Spanners with Steiner Points ⋮ Light spanners for high dimensional norms via stochastic decompositions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ramsey partitions and proximity data structures
• 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
• Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
• 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
• 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
• 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
• Light Spanners
• Higher Eigenvalues of 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
• Computing almost shortest paths
• A tight bound on approximating arbitrary metrics by tree metrics

This page was built for publication: