TomitaSekiMc
Declared in lemon/tomita_seki_mc.h, in the group Approximation Algorithms; the same class on the Doxygen site.
-
template< typename GR >
class TomitaSekiMc The exact maximum clique algorithm of Tomita and Seki.
This class finds a maximum clique of an undirected graph by the branch and bound of Tomita and Seki (MCQ): the candidates that may extend the current clique are colored greedily, so that those of the same color are not adjacent, and a branch is cut as soon as the current clique and the number of colors of its candidates cannot exceed the best clique found. Unlike GrossoLocatelliPullanMc, a heuristic, it proves that the clique it finds is maximum, in time that may grow exponentially with the size of the graph; a limit on the number of nodes of the search tree stops it early, with the best clique found.
- Template Parameters:
GR – The undirected graph type the algorithm runs on.
Query Functions
The results of the last run().
-
inline int cliqueSize() const
The size of the clique found.
-
inline long long treeSize() const
The number of nodes of the search tree of the last run.
Public Functions
-
inline explicit TomitaSekiMc( const GR & graph )
Constructor.
- Parameters:
graph – The undirected graph the algorithm runs on.
-
inline TomitaSekiMc & treeLimit( long long limit )
Set the limit on the nodes of the search tree.
This function sets the largest number of nodes of the search tree, i.e., of the cliques that the search extends, after which run() stops; a negative one, the default, is no limit.
-
inline bool run()
Run the algorithm.
- Returns:
trueif the clique found is proved maximum,falseif the limit on the search tree stopped the search first.