research
∙
04/10/2023
Path-Reporting Distance Oracles with Near-Logarithmic Stretch and Linear Size
Given an n-vertex undirected graph G=(V,E,w), and a parameter k≥1, a pat...
share
research
∙
04/29/2022
Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates
This paper presents efficient distributed algorithms for a number of fun...
research
∙
04/18/2022
Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications
This paper presents new deterministic and distributed low-diameter decom...
research
∙
07/28/2021
(1+ε)-Approximate Shortest Paths in Dynamic Streams
Computing approximate shortest paths in the dynamic streaming setting is...
research
∙
06/02/2021
Ultra-Sparse Near-Additive Emulators
Near-additive (aka (1+ϵ,β)-) emulators and spanners are a fundamental gr...
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/25/2019
Fast Deterministic Constructions of Linear-Size Spanners and Skeletons
In the distributed setting, the only existing constructions of sparse sk...
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/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
∙
03/03/2019
Near-Additive Spanners In Low Polynomial Deterministic CONGEST Time
Given parameters α≥ 1,β≥ 0, a subgraph G'=(V,H) of an n-vertex unweighte...
research
∙
02/22/2018
Near Isometric Terminal Embeddings for Doubling Metrics
Given a metric space (X,d), a set of terminals K⊆ X, and a parameter t> ...
research
∙
12/01/2017