bron_kerbosch

iqm.applications.mis.bron_kerbosch(mis_problem)

Bron-Kerbosch algorithm for finding the maximum independent set.

The algorithm finds all maximal cliques in a graph recursively. Cliques in complement graph correspond to independent sets in the problem graph. We pick the largest of these. For details see find_cliques — NetworkX documentation (and the references therein):

Parameters:

mis_problem (MISInstance | Graph) – A problem instance of maximum independent set or a Graph.

Returns:

A bitstring solution.

Return type:

str