论文标题
一轮分布式集团清单的改进结果的注释
A Note on Improved Results for One Round Distributed Clique Listing
论文作者
论文摘要
在本说明中，我们研究了带宽限制的动态网络中任意大小的列表。 Bonne and Censor-Hillel最初对检测和列表三角形和集团的发现问题（ICALP 2019）进行了详细研究。我们将这项研究扩展到了可能发生多个更新的动态图，并解决了Bonne和Censor-Hillel（2019）提出的一个开放问题。我们的算法和结果基于有关在各种设置下列出三角形的一些简单观察结果，我们表明我们可以使用此类事实列出较大的集团。具体来说，我们表明我们的技术可用于解决原始论文中提出的一个开放问题：我们表明，在节点插入和节点/边缘删除下进行一轮通信后，可以使用$ o（1）$ - 带宽进行检测和列表（任何大小）。最后，我们的技术扩展了，以获取一个小带宽$ 1 $ ROUND算法，用于列出集团时，当多个节点插入/删除和/或Edge删除更新随时发生。
In this note, we investigate listing cliques of arbitrary sizes in bandwidth-limited, dynamic networks. The problem of detecting and listing triangles and cliques was originally studied in great detail by Bonne and Censor-Hillel (ICALP 2019). We extend this study to dynamic graphs where more than one update may occur as well as resolve an open question posed by Bonne and Censor-Hillel (2019). Our algorithms and results are based on some simple observations about listing triangles under various settings and we show that we can list larger cliques using such facts. Specifically, we show that our techniques can be used to solve an open problem posed in the original paper: we show that detecting and listing cliques (of any size) can be done using $O(1)$-bandwidth after one round of communication under node insertions and node/edge deletions. We conclude with an extension of our techniques to obtain a small bandwidth $1$-round algorithm for listing cliques when more than one node insertion/deletion and/or edge deletion update occurs at any time.
