Nesetril, Poljak (k-Clique k-Clique Problem)
Revision as of 12:18, 15 February 2023 by Admin (talk | contribs) (Created page with "== 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")
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