Re: [boost] BGL: max clique?

From: Phlip (pplumlee_at_[hidden])
Date: 2001-03-04 13:24:08

Proclaimed Doug Gregor from the mountaintops:

> This problem is _very_ computationally intensive. The maximal clique
> problem is NP-complete already, and the maximum clique problem is even
> worse (can't be verified in polynomial time). In any case, don't expect a
> polynomial algorithm to solve either problem.

Oops. What's the difference between "maximal" and "maximum". Maybe the first 
is "find all nested KGraphs with a node count > X", and the second is "what's 
the biggest one?"

I just whipped out my /Combinatorics for Dummies/ book but it didn't have it.

> I've placed the tarball at http://www.cs.rpi.edu/~gregod/maxclique.tgz

Yes! Thanks!

The good news is our algorithmicist at work is about to blow your max clique 
algorithm out of the water. But the other good news is it's proprietary, so 
you'l have to either jump ship or wait 20 years to see how we did it. :-)

-- 
  Phlip                          phlip_cpp_at_[hidden]
============== http://phlip.webjump.com ==============
  --  "In my experience, the customer doesn't know what he wants
       until you don't give it to him." --David Brady  --