research
∙
07/21/2023
Improved Approximate Distance Oracles: Bypassing the Thorup-Zwick Bound in Dense Graphs
Despite extensive research on distance oracles, there are still large ga...
share
research
∙
07/14/2023
Õptimal Fault-Tolerant Reachability Labeling in Planar Graphs
We show how to assign labels of size Õ(1) to the vertices of a directed ...
research
∙
05/19/2023
Approximate Distance Sensitivity Oracles in Subquadratic Space
An f-edge fault-tolerant distance sensitive oracle (f-DSO) with stretch ...
research
∙
05/11/2023
Streaming Edge Coloring with Subquadratic Palette Size
In this paper, we study the problem of computing an edge-coloring in the...
research
∙
04/28/2020
Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem
In the Single Source Replacement Paths (SSRP) problem we are given a gra...
research
∙
10/12/2019
Reachability and Shortest Paths in the Broadcast CONGEST Model
In this paper we study the time complexity of the single-source reachabi...
research
∙
09/08/2019
Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time
In the fully dynamic maximal independent set (MIS) problem our goal is t...
research
∙
07/25/2019
Improved Girth Approximation and Roundtrip Spanners
In this paper we provide improved algorithms for approximating the girth...
research
∙
05/17/2019
Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles
In this work we derandomize two central results in graph algorithms, rep...
research
∙
03/31/2018
Optimal Distributed Coloring Algorithms for Planar Graphs in the LOCAL model
In this paper, we consider distributed coloring for planar graphs with a...
research
∙
11/17/2017