论文标题
$（1-ε）$ - 近似完全动态的密度子图：线性空间和更快的更新时间
$(1-ε)$-approximate fully dynamic densest subgraph: linear space and faster update time
论文作者
论文摘要
我们考虑了在无方向的多编码中维护$（1-ε）$ - 近似值（DSG）的问题，因为它经历了边缘插入和删除（完全动态的设置）。 Sawlani和Wang [SW20]开发了一个数据结构，对于任何给定的$ε> 0 $，它以$ O（\ log^4 n/ε^6）$ O（\ log^4 n/ε^6）$（$ o（1）$ O（1）$（1）$查询时间以报告密度值的时间。他们的数据结构是第一个实现近乎最佳近似的方法，并改进了以前的工作，该工作在摊销的polygarithmic更新时间中维持$（1/4-ε）$近似[BHNT15]。在本文中，我们为$（1-ε）$ - 近似DSG开发了一个数据结构，该数据结构在两个方面从[SW20]中提高了一个数据结构。首先，数据结构使用线性空间通过对数因素改善[SW20]中绑定的空间。其次，数据结构在摊销$ O（\ log^2 n/ε^4）$ o（\ log^2 n/ε^4）中维持$（1-ε）$ - 同时保证最坏的情况更新时间为$ O（\ log^3 n \ log \ log \ log \ log n/ε^6）$。我们认为，空间和更新时间的改进对于当前的大型图数据集很有价值。数据结构以自然方式扩展到超图表，并在[SW20]基于[BBCG22]的最新工作[BBCG22]中更新空间的改进和更新时间。
We consider the problem of maintaining a $(1-ε)$-approximation to the densest subgraph (DSG) in an undirected multigraph as it undergoes edge insertions and deletions (the fully dynamic setting). Sawlani and Wang [SW20] developed a data structure that, for any given $ε> 0$, maintains a $(1-ε)$-approximation with $O(\log^4 n/ε^6)$ worst-case update time for edge operations, and $O(1)$ query time for reporting the density value. Their data structure was the first to achieve near-optimal approximation, and improved previous work that maintained a $(1/4 - ε)$ approximation in amortized polylogarithmic update time [BHNT15]. In this paper we develop a data structure for $(1-ε)$-approximate DSG that improves the one from [SW20] in two aspects. First, the data structure uses linear space improving the space bound in [SW20] by a logarithmic factor. Second, the data structure maintains a $(1-ε)$-approximation in amortized $O(\log^2 n/ε^4)$ time per update while simultaneously guaranteeing that the worst case update time is $O(\log^3 n \log \log n/ε^6)$. We believe that the space and update time improvements are valuable for current large scale graph data sets. The data structure extends in a natural fashion to hypergraphs and yields improvements in space and update times over recent work [BBCG22] that builds upon [SW20].
