Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, and Isao Shirakawa (Enumerating Maximal Cliques, arbitrary graph Clique Problems)
Jump to navigation
Jump to search
Time Complexity
$O(nm)$ per clique
Space Complexity
$O(m)$ words
(See original reference, but also note that we'd have to construct and store the complementary graph (as this is originally an algo for MISs))
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
1977
Reference
https://www.proquest.com/docview/918487776?pq-origsite=gscholar&fromopenview=true