research
∙
08/24/2023
Are there graphs whose shortest path structure requires large edge weights?
The aspect ratio of a weighted graph G is the ratio of its maximum edge ...
share
research
∙
11/13/2022
A Local-to-Global Theorem for Congested Shortest Paths
Amiri and Wargalla (2020) proved the following local-to-global theorem i...
research
∙
07/10/2022
Closing the Gap Between Directed Hopsets and Shortcut Sets
For an n-vertex directed graph G = (V,E), a β-shortcut set H is a set of...
research
∙
04/06/2022
Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles
We study the approximability of two related problems: n-Pairs Shortest P...
research
∙
03/05/2022
Online List Labeling: Breaking the log^2n Barrier
The online list labeling problem is an algorithmic primitive with a larg...
research
∙
10/29/2021
Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product
We obtain improved lower bounds for additive spanners, additive emulator...
research
∙
03/11/2021
Hardness of Token Swapping on Trees
Given a graph where every vertex has exactly one labeled token, how can ...
research
∙
02/19/2021
Simple Combinatorial Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs
We revisit the minimum dominating set problem on graphs with arboricity ...
research
∙
11/08/2020
Tight Conditional Lower Bounds for Approximating Diameter in Directed Graphs
Among the most fundamental graph parameters is the Diameter, the largest...
research
∙
10/20/2020
New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners
Maintaining and updating shortest paths information in a graph is a fund...
research
∙
08/24/2020
Algorithms and Lower Bounds for the Worker-Task Assignment Problem
We study the problem of assigning workers to tasks where each task has d...
research
∙
06/30/2020
Lower Bounds for Dynamic Distributed Task Allocation
We study the problem of distributed task allocation in multi-agent syste...
research
∙
01/29/2020
New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs
In the dynamic Single-Source Shortest Paths (SSSP) problem, we are given...
research
∙
04/29/2019
Improved Dynamic Graph Coloring
This paper studies the fundamental problem of graph coloring in fully dy...
research
∙
04/25/2019
Approximation Algorithms for Min-Distance Problems
We study fundamental graph parameters such as the Diameter and Radius in...
research
∙
04/25/2019
Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
Some of the most fundamental and well-studied graph parameters are the D...
research
∙
11/29/2018
Algorithms and Hardness for Diameter in Dynamic Graphs
The diameter, radius and eccentricities are natural graph parameters. Wh...
research
∙
08/30/2018
Fully Dynamic MIS in Uniformly Sparse Graphs
We consider the problem of maintaining a maximal independent set (MIS) i...
research
∙
08/26/2018
Towards Tight Approximation Bounds for Graph Diameter and Eccentricities
Among the most important graph parameters is the Diameter, the largest d...
research
∙
04/20/2018