Listing Triangles
Listing Triangles
复制标题
列出三角形
DOI：
10.1007/978-3-662-43948-7_19
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Uri Zwick
中科院分区：
文献类型：
--
作者：
Andreas Björklund;R. Pagh;V. V. Williams;Uri Zwick
我们提出了新的算法，列出密集和稀疏图中的三角形。我们的算法对稠密图的运行时间为n（n + nt），对稀疏图的运行时间为n（m + mt），其中n为顶点数，m为边数，t为要列出的三角形数，ω < 2.373为快速矩阵乘法的指数。在ω的当前界下，算法的运行时间分别为<$（n+ nt）和<$（m+ mt）.我们首先获得所需的运行时间的随机算法，然后使用稀疏恢复技术去随机化。如果ω = 2，则算法的运行时间分别变为n（n + nt）和n（m+mt）。特别是，如果ω = 2，我们的算法会在³（m）时间内列出m个三角形。Ptrajeccu（STOC 2010）表明列出m个三角形需要Ω（m）时间，除非存在3SUM的次二次算法。我们表明，除非一个人可以解决二次方程系统在有限域上显着快于暴力算法，我们的三角形列表运行时的界限是紧的假设ω = 2，也为图形与更多的三角形。
We present new algorithms for listing triangles in dense and sparse graphs. The running time of our algorithm for dense graphs is Õ(n + nt), and the running time of the algorithm for sparse graphs is Õ(m + mt), where n is the number of vertices, m is the number of edges, t is the number of triangles to be listed, and ω < 2.373 is the exponent of fast matrix multiplication. With the current bound on ω, the running times of our algorithms are Õ(n+n t) and Õ(m+m t), respectively. We first obtain randomized algorithms with the desired running times and then derandomize them using sparse recovery techniques. If ω = 2, the running times of the algorithms become Õ(n + nt) and Õ(m+mt), respectively. In particular, if ω = 2, our algorithm lists m triangles in Õ(m) time. Pǎtraşcu (STOC 2010) showed that Ω(m) time is required for listing m triangles, unless there exist subquadratic algorithms for 3SUM. We show that unless one can solve quadratic equation systems over a finite field significantly faster than the brute force algorithm, our triangle listing runtime bounds are tight assuming ω = 2, also for graphs with more triangles.