CAR-CSIC, UPM, Madrid, Spain

Cliques and clique clusters is a fundamental decomposition in a network.  The first part of the talk will deal on the fundamental notions of k-core and vertex coloring decomposition for efficient large clique finding in big networks.  The next part of the talk will describe current research of the speaker related to the new algorithm BBMCS for the maximum clique problem. BBMCS is an extension of BBMC, an efficient state of the art algorithm for small and middle size networks, which includes specific data structures to deal with real networks. BBMCS will be shown to outperform other State of the Art algorithms in the comparative performance study presented at the end of the talk.

Seminar

Bit strings have proved to be an important source of efficiency when implementing algorithms for combinatorial optimization. Specifically in the graph domain, bit strings make up the core of BBMC and BBMCS, two reference algorithms for the maximum clique problem.

The seminar will include a description of BITSCAN, the speaker´s C++ library for bit strings, and GRAPH, a wrapper to bit-encode graphs using BITSCAN. Both of these libraries have recently been released. Moreover, specific code examples related to critical operations as used in BBMC and BBCMS (i.e. greedy coloring, subgraph generation etc.) will be presented and discussed.