Reactive Search: Maximum Clique

Contact us to buy or request information

The Maximum Clique problem in graphs asks for a clique of maximum size. A clique is a subset of nodes such that each node is connected to all other nodes of the subset. The picture below shows (in red) four nodes (3, 4, 5, 6) that are completely connected; these nodes are one clique of maximum size. Nodes 7, 8 and 9 are a clique but not of maximum size.

The Maximum Clique problem is a paradigmatic combinatorial optimization problem with relevant applications (in some cases considering variations of the above definitions), including information retrieval, computer vision, social network analysis, computational biochemistry, bio-informatics and genomics. The problem is very hard to solve exactly, making it an ideal test-bed for the application of Reactive Search.

The RS-MC library provides a simple way for the programmer to define the problem to be optimized in terms of a Maximum Clique instance, and to solve it using a powerful Reactive Search optimization.

The class library is useful to extend the Reactive Search solver and integrate it in your application and use it to solve optimization problems that are part of your workflow.

More details in the user manual.

Contact us to buy or request information