1. Home
    Item seperator
  3. Item seperator
    Finding a Maximum Clique In An Arbitrary Graph

Finding a Maximum Clique in an Arbitrary Graph

New Image

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, area (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.