Listing Triangles

Björklund, Andreas (author): Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH

Pagh, Rasmus (author)

Vassilevska Williams, Virginia (author)

Zwick, Uri (author)

Esparza, Javier (editor)

Fraigniaud, Pierre (editor)

Husfeldt, Thore (editor)

Koutsoupias, Elias (editor)

(creator_code:org_t)

Berlin, Heidelberg : Springer Berlin Heidelberg, 2014
2014
English 12 s.
In: Automata, Languages, and Programming (Lecture notes in computer science). - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. - 9783662439487 ; 8572, s. 223-234

Related links:: http://dx.doi.org/10...; show more...; https://lup.lub.lu.s...; https://doi.org/10.1...; show less...

Abstract Subject headings

We present new algorithms for listing triangles in dense and sparse graphs. The running time of our algorithm for dense graphs is O~(n^ω+n^3(ω−1)/(5−ω)t^2(3−ω)/(5−ω)), and the running time of the algorithm for sparse graphs is O~(m^2ω/(ω+1)+m^3(ω−1)/(ω+1)t^(3−ω)/(ω+1)), 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 O~(n^2.373+n^1.568t^0.478) and O~(m^1.408+m^1.222t^0.186), 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 O~(n^2+nt^2/3) and O~(m^4/3+mt^1/3), respectively. In particular, if ω = 2, our algorithm lists m triangles in O~(m4/3) time. Pǎtraşcu (STOC 2010) showed that Ω(m^(4/3 − o(1))) 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.

By the author/editor: Björklund, Andre ...; Pagh, Rasmus; Vassilevska Will ...; Zwick, Uri; Esparza, Javier; Fraigniaud, Pier ...; show more...; Husfeldt, Thore; Koutsoupias, Eli ...; show less...

About the subject

NATURAL SCIENCES: NATURAL SCIENCES; and Computer and Inf ...; and Computer Science ...

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.