research
∙
08/01/2023
Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-f Time Barrier
The dynamic set cover problem has been subject to extensive research sin...
share
research
∙
07/31/2023
Shortcut Partitions in Minor-Free Graphs: Steiner Point Removal, Distance Oracles, Tree Covers, and More
The notion of shortcut partition, introduced recently by Chang, Conroy, ...
research
∙
07/05/2023
Density-Sensitive Algorithms for (Δ+ 1)-Edge Coloring
Vizing's theorem asserts the existence of a (Δ+1)-edge coloring for any ...
research
∙
06/20/2023
Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the Ω(log n) Lightness Barrier
An essential requirement of spanners in many applications is to be fault...
research
∙
06/09/2023
Resolving the Steiner Point Removal Problem in Planar Graphs via Shortcut Partitions
Recently the authors [CCLMST23] introduced the notion of shortcut partit...
research
∙
06/09/2023
Covering Planar Metrics (and Beyond): O(1) Trees Suffice
While research on the geometry of planar graphs has been active in the p...
research
∙
12/16/2021
Sparse Euclidean Spanners with Tiny Diameter: A Tight Lower Bound
In STOC'95 [ADMSS'95] Arya et al. showed that any set of n points in ℝ^d...
research
∙
11/26/2021
A Unified Framework of Light Spanners II: Fine-Grained Optimality
Seminal works on light spanners over the years provide spanners with opt...
research
∙
08/19/2021
Maintaining an EDCS in General Graphs: Simpler, Density-Sensitive and with Worst-Case Time Bounds
In their breakthrough ICALP'15 paper, Bernstein and Stein presented an a...
research
∙
07/30/2021
Near-Optimal Spanners for General Graphs in (Nearly) Linear Time
Let G = (V,E,w) be a weighted undirected graph on |V| = n vertices and |...
research
∙
07/29/2021
Can't See The Forest for the Trees: Navigating Metric Spaces by Bounded Hop-Diameter Spanners
Spanners for metric spaces have been extensively studied, both in genera...
research
∙
06/29/2021
Towards a Unified Theory of Light Spanners I: Fast (Yet Optimal) Constructions
Seminal works on light spanners over the years provide spanners with opt...
research
∙
05/14/2021
Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach
In the (fully) dynamic set cover problem, we have a collection of m sets...
research
∙
05/05/2021
Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs
In graph sparsification, the goal has almost always been of global natur...
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
∙
10/30/2020
Dynamic Distributed MIS with Improved Bounds
The problem of maintaining a maximal independent set (MIS) in a dynamic ...
research
∙
08/24/2020
A Unified and Fine-Grained Approach for Light Spanners
Seminal works on light spanners from recent years provide near-optimal t...
research
∙
07/22/2020
Light Euclidean Spanners with Steiner Points
The FOCS'19 paper of Le and Solomon, culminating a long line of research...
research
∙
06/13/2020
When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear-Time
Maximal independent set (MIS), maximal matching (MM), and (Δ+1)-coloring...
research
∙
10/04/2019
Fully Dynamic (Δ+1)-Coloring in Constant Update Time
The problem of (vertex) (Δ+1)-coloring a graph of maximum degree Δ has b...
research
∙
04/29/2019
Improved Dynamic Graph Coloring
This paper studies the fundamental problem of graph coloring in fully dy...
research
∙
04/26/2019
Truly Optimal Euclidean Spanners
Euclidean spanners are important geometric structures, having found nume...
research
∙
08/30/2018
Fully Dynamic MIS in Uniformly Sparse Graphs
We consider the problem of maintaining a maximal independent set (MIS) i...
research
∙
06/26/2018
Fully Dynamic Maximal Independent Set with Sublinear in n Update Time
The first fully dynamic algorithm for maintaining a maximal independent ...
research
∙
03/15/2018
Dynamic Approximate Matchings with an Optimal Recourse Bound
In the area of dynamic matching algorithms, the number of changes to the...
research
∙
02/27/2018
Fully Dynamic Maximal Independent Set with Sublinear Update Time
A maximal independent set (MIS) can be maintained in an evolving m-edge ...
research
∙
02/26/2018
Representations of Sparse Distributed Networks: A Locality-Sensitive Approach
In 1999, Brodal and Fagerberg (BF) gave an algorithm for maintaining a l...
research
∙
02/20/2018
Wireless Expanders
This paper introduces an extended notion of expansion suitable for radio...
research
∙
11/18/2017