zbMATH — the first resource for mathematics

Finding a maximum clique in an arbitrary graph. (English) Zbl 0604.05024
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; (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.

MSC:
 05C35 Extremal problems in graph theory 68R10 Graph theory (including graph drawing) in computer science 05-04 Software, source code, etc. for problems pertaining to combinatorics
Full Text: