×

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
PDF BibTeX XML Cite
Full Text: DOI