Approximate Fully Dynamic Directed Densest Subgraph

Richard Li, Kent Quanrud

We give a fully dynamic algorithm maintaining a $(1-\epsilon )$-approximate directed densest subgraph in $\tilde{O}({\log }^3(n)/{\epsilon }^6)$ amortized time or $\tilde{O}(\log^4(…