<p>I think MinG's opinion about solving the maximum clique problem efficiently using branch and bound method on sparse graphs, is fully supported by the paper of Rossi, Gleich and Gebremedhin <a href="http://arxiv.org/abs/1302.6256" rel="nofollow">http://arxiv.org/abs/1302.6256</a> . They show that with heavy pruning, the maximum clique can be found really quickly on sparse graphs (even though they may be really huge). </p>

<p>Of course the problem still remains NP-Complete, but since it can be scalable on graphs with millions of edges, one might say that branch and bound methods might be promising on this problem.</p>
How to find the maximum edge-weighted clique?
<p>The maximum clique problem (MC-problem) is a classical NP problem, and we could use branch-bound to solve this problem effectively. Recently, I try to develop an algorithm to find out the clique that has the maximum edge-weighted clique in a graph, as we know, maximum edge-weighted clique problem (MEC-problem). </p>

<p>I have found some properties about this problem. First, the clique must be a maximal clique which does not belong to any larger clique. Then the sum of edges of the clique must be the largest of all maximal clique.</p>

<p>However, traditional algorithm of MC-problem will not be effective on MEC-problem. Therefore, I want to find an effective algorithm on MEC-problem, especially branch-bound algorithm.</p>