Talk:Clique problem

From Wikipedia, the free encyclopedia

You have new messages (last change).

I thought a clique was a fully connected sub-graph? The way it is described here makes me think a clique is two adjacent vertices... --Bryanlharris 19:21, May 7, 2004 (UTC)

Pairwise adjacent means every pair of vertices in the set are adjacent. This is equivalent to your definition. Deco 19:38, 26 Mar 2005 (UTC)

[edit] Proposed move

I propose we move this to maximum clique problem, which is a commonly used name that is more accurate and specific. I put a redirect in the way, but I'll take care of the move if there's consent. Deco 23:58, 27 May 2005 (UTC)

Seems like a reasonable idea. MathMartin 09:05, 28 May 2005 (UTC)

[edit] Removed proof

I removed the proof that maximum clique is NP-complete and replaced it by an appeal to the NP-completeness of independent set. It was a good proof, but I think it's easier to go through independent set, because there's a lot less edges to talk about filling in. Admittedly the proof on independent set problem isn't all that nice, and any improvement to it would be great. Deco 01:49, 8 Jun 2005 (UTC)

Rewrote independent set problem now. Should be somewhat better. Deco 04:47, 8 Jun 2005 (UTC)
Retrieved from "http://en.wikipedia.org../../../c/l/i/Talk%7EClique_problem_6e6c.html"