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
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 --
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk