# Clique Enumeration Algorithm

I am reading an old paper of M.C. Golumbic about EPT (edge intersection of paths in a tree) graphs. In the paper it is shown that the number of maximal cliques of an EPT graph instance is polynomial. It concludes that if an oracle reports that a graph $G$ is an EPT graph, then it is possible to find the maximum clique with a standard clique enumeration algorithm.

First of all, what are these standard clique enumeration algorithms? If there are more than one, can we say that if the number of maximal cliques of a graph is polynomial then can we use any of these enumeration algorithms? Or should we derive a special algorithm from a generic algorithm which uses some special structures of the graph class?

• To get the $O(3^{n/3})$ bound, we need a little trick for effectively performing branch-and-bound in the backtracking procedure (due to Tomita, Tanaka, and Takahashi). It's also good to note that the bound of $3^{n/3}$ is worst-case optimal, since there is a graph with $3^{n/3}$ maximal cliques (namely, $K_{3,3,...,3}$). – Yoshio Okamoto Dec 3 '11 at 16:01