research
∙
07/18/2023
Fast 2-Approximate All-Pairs Shortest Paths
In this paper, we revisit the classic approximate All-Pairs Shortest Pat...
share
research
∙
11/09/2022
A Nearly Time-Optimal Distributed Approximation of Minimum Cost k-Edge-Connected Spanning Subgraph
The minimum-cost k-edge-connected spanning subgraph (k-ECSS) problem is ...
research
∙
11/02/2022
New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
We provide new tradeoffs between approximation and running time for the ...
research
∙
06/10/2022
Near-Optimal Distributed Dominating Set in Bounded Arboricity Graphs
We describe a simple deterministic O( ε^-1logΔ) round distributed algori...
research
∙
06/01/2021
Fault-Tolerant Labeling and Compact Routing Schemes
The paper presents fault-tolerant (FT) labeling schemes for general grap...
research
∙
04/20/2020
Distributed Weighted Min-Cut in Nearly-Optimal Time
Minimum-weight cut (min-cut) is a basic measure of a network's connectiv...
research
∙
03/06/2020
Exponentially Faster Shortest Paths in the Congested Clique
We present improved deterministic algorithms for approximating shortest ...
research
∙
03/02/2020
Massively Parallel Algorithms for Distance Approximation and Spanners
Over the past decade, there has been increasing interest in distributed/...
research
∙
05/26/2019
Improved Distributed Approximations for Minimum-Weight Two-Edge-Connected Spanning Subgraph
The minimum-weight 2-edge-connected spanning subgraph (2-ECSS) problem i...
research
∙
05/24/2019
Hardness of Distributed Optimization
This paper studies lower bounds for fundamental optimization problems in...
research
∙
03/14/2019
Fast Approximate Shortest Paths in the Congested Clique
We design fast deterministic algorithms for distance computation in the ...
research
∙
05/20/2018
Distributed Approximation of Minimum k-edge-connected Spanning Subgraphs
In the minimum k-edge-connected spanning subgraph (k-ECSS) problem the g...
research
∙
02/09/2018
Distributed Spanner Approximation
We address the fundamental network design problem of constructing approx...
research
∙
11/09/2017
