Approximate Fully Dynamic Directed Densest Subgraph

2023/12/13 by Li, Richard, Quanrud, Kent
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2312.07827

Abstract

We give a fully dynamic algorithm maintaining a (1-ε)-approximate directed densest subgraph in O(log³(n)/ε⁶) amortized time or O(log⁴(n)/ε⁷) worst-case time per edge update (where O hides loglog factors), based on earlier work by Chekuri and Quanrud [arXiv:2210.02611, arXiv:2310.18146]. This result improves on earlier work done by Sawlani and Wang [arXiv:1907.03037], which guarantees O(log⁵(n)/ε⁷) worst case time for edge insertions and deletions.

Related

• Near-Optimal Fully Dynamic Densest Subgraph
• (1-ε)-approximate fully dynamic densest subgraph: linear space and faster update time
• A New Dynamic Algorithm for Densest Subhypergraphs
• Densest Subgraph in Dynamic Graph Streams
• Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on\n One-Pass Dynamic Streams