$(1-\epsilon )$-approximate fully dynamic densest subgraph: linear space and faster update time

Chandra Chekuri, Kent Quanrud

We consider the problem of maintaining a $(1-\epsilon )$-approximation to the densest subgraph (DSG) in an undirected multigraph as it undergoes edge insertions and deletions (the fully dy…