How Proofs are Prepared at Camelot
Författare
Summary, in English
As our main technical result, we show that the k-cliques in an n-vertex graph can be counted and verified in per-node O(n(ω+ε)k/6) time and space on O(n(ω+ε)k/6) compute nodes, for any constant ε>0 and positive integer k divisible by 6, where 2 ≤ ω < 2.3728639 is the exponent of square matrix multiplication over the integers. This matches in total running time the best known sequential algorithm, due to Nešetřil and Poljak [Comment. Math. Univ. Carolin. 26 (1985) 415--419], and considerably improves its space usage and parallelizability. Further results (only partly presented in this extended abstract) include novel algorithms for counting triangles in sparse graphs, computing the chromatic polynomial of a graph, and computing the Tutte polynomial of a graph.
Avdelning/ar
Publiceringsår
2016
Språk
Engelska
Sidor
391-400
Publikation/Tidskrift/Serie
PODC '16 Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing
Dokumenttyp
Konferensbidrag
Förlag
Association for Computing Machinery (ACM)
Ämne
- Computer Science
Conference name
ACM Symposium on Principles of Distributed Computing (PODC '16)
Conference date
2016-07-25 - 2016-07-28
Conference place
Chicago, United States
Status
Published
ISBN/ISSN/Övrigt
- ISBN: 978-1-4503-3964-3