Triangle Counting in Large Sparse Graph
Date Issued
2008
Date
2008
Author(s)
Tsai, Meng-Tsung
Abstract
In this paper, we develop a new algorithm to count the number of triangles in a graph $G(n, m)$.he latest efficient algorithm, Forward Algorithm, needs $O(m^{3/2})$ basic instructions'' execution timend $Theta(m)$ memory space.ith the combination of the well-known Four-Russians'' Algorithm, we obtain an algorithm that requiresO(m^{3/2}/log^{1/2} m)$ execution of the population count procedure using $Theta(m)$ memory space.ome CPUs support population count directly.n such cases, the population count can be executed with one instruction;therwise, an alternative method should be employed.he known best one is named as extit{bitwise twiddling} method,hich can be executed with $Theta(log^{(2)}g)$ basic instructions.wing to it is not necessary to exactly know the result of each population count, we can replaceach population count with an amortized population count.herefore, we also develop an efficient algorithm to fast execute the amortized population count.ased on the theoretic analysis, we conclude that the amortized population count can be executed witho(log^{(3)}g)$ basic instructions.esides, the experiment result also shows the performance of our amortized population count is betterhan others.s a result, our triangle counting algorithm is faster than the previous known best one by factor $omega(g^{1/2} / log^{(3)} g)$ where $g = Omega(log m)$.
Subjects
triangle counting
sparse graph
efficient algorithm
population counting
frequency division principle
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-97-R95922065-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):6a6aea1765c0e021bd5fdd12e4318bdf