Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, and Isao Shirakawa (Enumerating Maximal Cliques, arbitrary graph Clique Problems)

From Algorithm Wiki
Revision as of 11:15, 15 February 2023 by Admin (talk | contribs) (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...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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&fromopenview=true

Retrieved from "https://algorithm-wiki.csail.mit.edu/w/index.php?title=Shuji_Tsukiyama,_Mikio_Ide,_Hiromu_Ariyoshi,_and_Isao_Shirakawa_(Enumerating_Maximal_Cliques,_arbitrary_graph_Clique_Problems)&oldid=45413"