2015/05/08 by C. Seshadhri, Seshadhri, C. · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.1505.01927
openalex publication_date 2015/05/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A recent result of Eden, Levi, and Ron (ECCC 2015) provides a sublinear time algorithm to estimate the number of triangles in a graph. Given an undirected graph G, one can query the degree of a vertex, the existence of an edge between vertices, and the ith neighbor of a vertex. Suppose the graph has n vertices, m edges, and t triangles. In this model, Eden et al provided a O(\poly(\eps-1log n)(n/t1/3 + m3/2/t)) time algorithm to get a (1+\eps)-multiplicative approximation for t, the triangle count. This paper provides a simpler algorithm with the same running time (up to differences in the \poly(\eps-1log n) factor) that has a substantially simpler analysis.