7 citations · 16 across the 30 of their papers we have counts for
4 papers · 1 filter
Constructing Light Spanners Deterministically in Near-Linear Time
Stephen Alstrup, Søren Dahlgaard, Arnold Filtser +2
Graph spanners are well-studied and widely used both in theory and practice. In a recent breakthrough, Chechik and Wulff-Nilsen [CW18] improved the state-of-the-art for light spann…
Metric Embedding via Shortest Path Decompositions
Ittai Abraham, Arnold Filtser, Anupam Gupta +1
We study the problem of embedding shortest-path metrics of weighted graphs into spaces. We introduce a new embedding technique based on low-depth decompositions of a graph…
Ramsey Spanning Trees and their Applications
Ittai Abraham, Shiri Chechik, Michael Elkin +2
The metric Ramsey problem asks for the largest subset of a metric space that can be embedded into an ultrametric (more generally into a Hilbert space) with a given distortion.…
Steiner Point Removal with Distortion
Arnold Filtser
In the Steiner point removal (SPR) problem, we are given a weighted graph and a set of terminals of size . The objective is to find a minor of wit…