English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the problem of maintaining a $(1-\epsilon)$-approximation to thedensest subgraph (DSG) in an undirected multigraph as it undergoes edgeinsertions and deletions (the fully dynamic setting). Sawlani and Wang [SW20]developed a data structure that, for any given $\epsilon > 0$, maintains a$(1-\epsilon)$-approximation with $O(\log^4 n/\epsilon^6)$ worst-case updatetime for edge operations, and $O(1)$ query time for reporting the densityvalue. Their data structure was the first to achieve near-optimalapproximation, and improved previous work that maintained a $(1/4 - \epsilon)$approximation in amortized polylogarithmic update time [BHNT15]. In this paperwe develop a data structure for $(1-\epsilon)$-approximate DSG that improvesthe one from [SW20] in two aspects. First, the data structure uses linear spaceimproving the space bound in [SW20] by a logarithmic factor. Second, the datastructure maintains a $(1-\epsilon)$-approximation in amortized $O(\log^2n/\epsilon^4)$ time per update while simultaneously guaranteeing that the worstcase update time is $O(\log^3 n \log \log n/\epsilon^6)$. We believe that thespace and update time improvements are valuable for current large scale graphdata sets. The data structure extends in a natural fashion to hypergraphs andyields improvements in space and update times over recent work [BBCG22] thatbuilds upon [SW20].

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