Listing Triangles
Författare
Redaktör
- Javier Esparza
- Pierre Fraigniaud
- Thore Husfeldt
- Elias Koutsoupias
Summary, in English
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.
Avdelning/ar
Publiceringsår
2014
Språk
Engelska
Sidor
223-234
Publikation/Tidskrift/Serie
Automata, Languages, and Programming (Lecture notes in computer science)
Volym
8572
Dokumenttyp
Konferensbidrag
Förlag
Springer
Ämne
- Computer Science
Conference name
International Colloquium, ICALP 2014
Conference date
2014-07-08 - 2014-07-11
Conference place
Copenhagen, Denmark
Status
Published
Projekt
- Exact algorithms
Forskningsgrupp
- Algorithms
ISBN/ISSN/Övrigt
- ISSN: 0302-9743
- ISSN: 1611-3349
- ISBN: 978-3-662-43948-7