Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, and Isao Shirakawa (Enumerating Maximal Cliques, arbitrary graph Clique Problems): Difference between revisions
Jump to navigation
Jump to search
(Created page with "== Time Complexity == $O(nm)$ per clique == Space Complexity == $O(m)$ auxiliary 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&fromopenv...") |
No edit summary |
||
| Line 5: | Line 5: | ||
== Space Complexity == | == Space Complexity == | ||
$O(m)$ | $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)) | (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)) | ||
Latest revision as of 08:43, 10 April 2023
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