Structural Bioinformatics Library
Template C++ / Python API for developping structural bioinformatics applications.
List of all members
T_Maximum_clique_finder< GraphType > Class Template Reference
Reference Manuals » Maximum_clique

Functor returning the vertices of a maximum clique of an input graph. More...

#include <Maximum_clique_finder.hpp>

Detailed Description

template<class GraphType>
class SBL::CADS::T_Maximum_clique_finder< GraphType >

Functor returning the vertices of a maximum clique of an input graph.

Given a boost graph, will find a maximum cardinality clique using P.R.J Ostergard algorithm.

  • Vertex colours are approximated using sequential vertex colouring
  • Time limit is not implemented

It is inspired from "A fast algorithm for the maximum clique problem", P. R. J. Östergård, Discrete Applied Mathematics 120 (2002), 197-207. The only difference is that here the number of colours in the neighbourhood of a vertex is crudely approximated.

Template Parameters
GraphModel of an undirected boost graph with vector for storing the vertices and the edges.