论文标题
改进了以任意顺序计数4循环计数4循环的三通算法
Improved 3-pass Algorithm for Counting 4-cycles in Arbitrary Order Streaming
论文作者
论文摘要
在流媒体模型中，计算小型子图，特别是周期的问题在过去几年中引起了很多关注。在本文中，我们考虑了任意订单插入的流，对计算4个周期的最新结果改善。我们的算法通过在流上进行三个通行并使用Space $ O（\ frac {m \ log n} {ε^2 t^{1/3}}）$来计算$（1+ε）$ - 近似值，其中$ m $是图中的边缘数，$ t $是$ t $的数量。
The problem of counting small subgraphs, and specifically cycles, in the streaming model received a lot of attention over the past few years. In this paper, we consider arbitrary order insertion-only streams, improving over the state-of-the-art result on counting 4-cycles. Our algorithm computes a $(1+ε)$-approximation by taking three passes over the stream and using space $O(\frac{m \log n}{ε^2 T^{1/3}})$, where $m$ is the number of edges in the graph and $T$ is the number of 4-cycles.
