research
∙
07/31/2023
Light, Reliable Spanners
A ν-reliable spanner of a metric space (X,d), is a (dominating) graph H,...
share
research
∙
08/22/2021
A Unified Framework for Hopsets and Spanners
Given an undirected graph G=(V,E), an (α,β)-spanner H=(V,E') is a subgra...
research
∙
08/22/2020
Improved Weighted Additive Spanners
Graph spanners and emulators are sparse structures that approximately pr...
research
∙
04/16/2020
Centralized and Parallel Multi-Source Shortest Paths via Hopsets and Fast Matrix Multiplication
Consider an undirected weighted graph G = (V,E,w). We study the problem ...
research
∙
01/21/2020
Near-Additive Spanners and Near-Exact Hopsets, A Unified View
Given an unweighted undirected graph G = (V,E), and a pair of parameter...
research
∙
07/26/2019
Almost Shortest Paths and PRAM Distance Oracles in Weighted Graphs
Let G=(V,E) be a weighted undirected graph with n vertices and m edges, ...
research
∙
07/16/2019
Lossless Prioritized Embeddings
Given metric spaces (X,d) and (Y,ρ) and an ordering x_1,x_2,...,x_n of (...
research
∙
05/18/2019
Covering Metric Spaces by Few Trees
A tree cover of a metric space (X,d) is a collection of trees, so that ...
research
∙
05/07/2019
Distributed Construction of Light Networks
A t- spanner H of a weighted graph G=(V,E,w) is a subgraph that approxim...
research
∙
04/20/2018
Light Spanners for High Dimensional Norms via Stochastic Decompositions
Spanners for low dimensional spaces (e.g. Euclidean space of constant di...
research
∙
02/22/2018