Enumerating Maximal Cliques, arbitrary graph

A maximal clique (complete subgraph) is a clique that is not contained in any other clique. The goal here is to enumerate such maximal cliques in a given graph.

Parameters

$n$ : number of vertices
$m$ : number of edges

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 9 of 9 algorithms


David Eppstein, Maarten Löffler, Darren Strash	2010	$O(dn 3^{d/3})$	$O(n^2)$
Tomita; Tanaka & Takahashi	2006	$O(3^{n/3})$	$O(n^2)$
Kazuhisa Makino, Takeaki Uno; Section 5	2004	$O(n^{\omega})$ per clique	$O(n^2)$
Kazuhisa Makino, Takeaki Uno; Section 6	2004	O(delta^4)	O(n+m) auxiliary()
M. Chrobak and D. Eppstein	1989	$O(n d^2 2^d)$	$O(n)$
Chiba and Nishizeki	1985	$O(a(G)m)$ per clique	$O(m)$
Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, and Isao Shirakawa	1977	$O(nm)$ per clique	$O(m)$
Bron–Kerbosch algorithm	1973	$O(3^{n/3})$	$O(n^2)$
Akkoyunlu; E. A.	1973	$O(3^{n/3})$	$O(n^2)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Displaying 1 of 1 other relevant algorithms