We describe a new type of branch and bound procedure for finding a maximum clique in an arbitrary graph $G = (V,E)$. The two main ingredients, both of $O(|V| + |E|)$ time complexity, are (i) an algorithm for finding a maximal triangulated induced subgraph of G; and (ii) an algorithm for finding a maximal k-chromatic induced subgraph of G. We discuss computational experience on randomly generated graphs with up to 400 vertices and 30,000 edges.
No takes yet. Share an insight, caveat, or question.
Balas et al. (1986) studied this question.
Synapse has enriched 4 closely related papers on similar clinical questions. Consider them for comparative context: