Sökning: onr:"swepub:oai:lup.lub.lu.se:a03045ea-61e6-4d67-b403-21435077caf9" >
Listing Triangles
Listing Triangles
-
- Björklund, Andreas (författare)
- 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 (författare)
-
Vassilevska Williams, Virginia (författare)
-
visa fler...
-
Zwick, Uri (författare)
-
Esparza, Javier (redaktör/utgivare)
-
Fraigniaud, Pierre (redaktör/utgivare)
-
Husfeldt, Thore (redaktör/utgivare)
-
Koutsoupias, Elias (redaktör/utgivare)
-
visa färre...
-
(creator_code:org_t)
- Berlin, Heidelberg : Springer Berlin Heidelberg, 2014
- 2014
- Engelska 12 s.
-
Ingår i: Automata, Languages, and Programming (Lecture notes in computer science). - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. - 9783662439487 ; 8572, s. 223-234
- Relaterad länk:
-
http://dx.doi.org/10...
-
visa fler...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publikations- och innehållstyp
- kon (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas