Nesetril, Poljak (k-Clique k-Clique Problem)
Jump to navigation
Jump to search
Time Complexity
$O(n^(k-({3}-\omega)*floor(k/{3}))$ where omega is the exponent on matrix multiplication
Space Complexity
$O(n^({2}k/{3})$) ish words
(matrix sizes)
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
1985
Reference
https://dml.cz/bitstream/handle/10338.dmlcz/106381/CommentatMathUnivCarol_026-1985-2_22.pdf