The 3SUM conjecture has proven to be a valuable tool for proving conditional lower bounds
on dynamic data structures and graph problems. This line of work was initiated by Pâtraşcu …

Baswana, Gupta and Sen [FOCS'11] showed that fully dynamic maximal matching can be
maintained in general graphs with logarithmic amortized update time. More specifically …

Maximum cardinality matching is a fundamental algorithmic problem with many algorithms
and applications. The fully dynamic version, in which edges are inserted and deleted over …

We give the first fully dynamic algorithm which maintains a (1− є)-approximate densest
subgraph in worst-case time poly (log n, є− 1) per update. Dense subgraph discovery is an …

We present two fully dynamic algorithms for maximum cardinality matching in bipartite
graphs. Our main result is a deterministic algorithm that maintains a (3/2+ ϵ)(3/2+ ϵ) …

We consider the problem of maintaining an approximately maximum (fractional) matching
and an approximately minimum vertex cover in a dynamic graph. Starting with the seminal …

We present a framework for deterministically rounding a dynamic fractional matching.
Applying our framework in a black-box manner on top of existing fractional matching …

Consider the following distance query for an n-node graph G undergoing edge insertions
and deletions: given two sets of nodes I and J, return the distances between every pair of …

The dynamic shortest paths problem on planar graphs asks us to preprocess a planar graph
G such that we may support insertions and deletions of edges in G as well as distance …

This article studies the fundamental problem of graph coloring in fully dynamic graphs. Since
the problem of computing an optimal coloring, or even approximating it to within n1-ε for any …