Variations on a matching based clique finding procedure
E. Bales, William Niehaus · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 1994
We discuss a procedure based on bipartite matching for generating large cliques in an arbitrary graph G = (V, E). After generating an initial set of cliques, we take every pair of cliques in the set and use bipartite matching to find a maximum clique in the subgraph induced by the nodes of the pair. We then recursively apply this procedure to the new clique set generated. We discuss variants like using bipartite matching to find all maximum cliques in the subgraph induced by the node of a pair of cliques. Computational results are reported on the DIMACS supplied benchmarks and other test problems, as well as comparisons with 2 other heuristics.