Light spanners for high dimensional norms via stochastic decompositions
type: Item
instance of: scholarly article
title: Light spanners for high dimensional norms via stochastic decompositions
author: Arnold Filtser
author: Ofer Neiman
published in: Algorithmica
publication date: 2022-10-06T00:00:00Z
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
zbMATH DE Number: 7596609
zbMATH Keywords: spanners
zbMATH Keywords: stochastic decompositions
zbMATH Keywords: high dimensional euclidean space
zbMATH Keywords: doubling dimension
zbMATH Keywords: genus graphs
zbMATH Keywords: treewidth
MaRDI profile type: Publication
full work available at URL: s00453-022-00994-0
OpenAlex ID: W2962701863
cites work: Advances in metric embedding theory
cites work: Graph spanners: a tutorial review
cites work: Ramsey Spanning Trees and Their Applications
cites work: On sparse spanners of weighted graphs
cites work: Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs
cites work: Complexity of network synchronization
cites work: Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
cites work: Greedy spanners are optimal in doubling metrics
cites work: NEW SPARSENESS RESULTS ON GRAPH SPANNERS
cites work: Sparse Sourcewise and Pairwise Distance Preservers
cites work: Approximation Algorithms for the 0-Extension Problem
cites work: Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
cites work: Near-Optimal Light Spanners
cites work: Distributed Construction of Light Networks
cites work: Computing almost shortest paths
cites work: Light Spanners
cites work: Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
cites work: Graph distances in the streaming model: the value of space
cites work: Clan embeddings into trees, and low treewidth graphs
cites work: Q5009588
cites work: A tight bound on approximating arbitrary metrics by tree metrics
cites work: On the optimality of the random hyperplane rounding technique for MAX CUT
cites work: The Greedy Spanner is Existentially Optimal
cites work: Q2754203
cites work: Q3757929
cites work: Euclidean Spanners in High Dimensions
cites work: Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
cites work: A subset spanner for Planar graphs, with application to subset TSP
cites work: Measured descent: A new embedding method for finite metrics
cites work: Higher Eigenvalues of Graphs
cites work: Excluded minors, network decomposition, and multicommodity flow
cites work: The geometry of graphs and some of its algorithmic applications
cites work: Extending Lipschitz functions via random metric partitions
cites work: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
cites work: Low diameter graph decompositions
cites work: Q5417618
cites work: Truly Optimal Euclidean Spanners
cites work: Ramsey partitions and proximity data structures
cites work: Geometric Spanner Networks
cites work: Q4944965
cites work: Distributed Computing: A Locality-Sensitive Approach
cites work: Q5090437
cites work: An Optimal Synchronizer for the Hypercube
cites work: A trade-off between space and efficiency for routing tables
cites work: Automata, Languages and Programming
cites work: Algorithms – ESA 2004
cites work: The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension
cites work: Bypassing the embedding
cites work: Approximate distance oracles
cites work: A sparse graph almost as good as the complete graph on points in \(k\) dimensions
cites work: Light graphs with small routing cost
DOI: 10.1007/S00453-022-00994-0
description: scientific article; zbMATH DE number 7596609