Omnia vincit amor
Home -> Publications
Home
  Publications
    
edited volumes
  Awards
  Research
  Teaching
  Miscellaneous
  Full CV [pdf]
  BLOG






  Events








  Past Events





Publications of Torsten Hoefler
Lukas Gianinazzi, Maciej Besta, Yannick Schaffner, Torsten Hoefler:

 Parallel Algorithms for Finding Large Cliques in Sparse Graphs

(In Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'21), ACM, Jul. 2021)

Abstract

We present a parallel k-clique listing algorithm with improved work bounds (for the same depth) in sparse graphs with low degeneracy or arboricity. We achieve this by introducing and analyzing a new pruning criterion for a backtracking search. Our algorithm has better asymptotic performance, especially for larger cliques (when k is not constant), where we avoid the straightforwardly exponential runtime growth with respect to the clique size. In particular, for cliques that are a constant factor smaller than the graph's degeneracy, the work improvement is an exponential factor in the clique size compared to previous results. Moreover, we present a low-depth approximation to the community degeneracy (which can be arbitrarily smaller than the degeneracy). This approximation enables a low depth clique listing algorithm whose runtime is parameterized by the community degeneracy.

Documents

download article:     


Recorded talk (best effort)

 

BibTeX

@inproceedings{gianinazzi-spaa21-KClique,
  author={Lukas Gianinazzi and Maciej Besta and Yannick Schaffner and Torsten Hoefler},
  title={{Parallel Algorithms for Finding Large Cliques in Sparse Graphs}},
  year={2021},
  month={Jul.},
  booktitle={Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'21)},
  publisher={ACM},
  source={http://www.unixer.de/~htor/publications/},
}


serving: 34.226.141.207:41520© Torsten Hoefler