Reputation: 6557
Is there a freely available implementation of finding a maximum weight clique in weighted graph in C#?
Upvotes: 1
Views: 1885
Reputation: 67
You could read the paper "A fast algorithm for the maximum clique problem", and you will find an effective maximum clique algorithm that proposed in this paper. In addition, a maximum weighted algorithm could be found in "A new algorithm for the maximum weighted clique problem". Here is the Pseudo-Code:
1 **FUNCTION CLIQUE(U, size)**
2 if |U| = 0 then
3 if size > max then
4 max ← size
5 New record; save it.
6 found ← true
7 end
8 return
9 end
10 while |U| != ∅ do
11 if size + weight(|U|) <= max then
12 return
13 end
14 i ← min{ j|vj ∈ U}
15 if size + c[i] <= max then
16 return
17 end
18 U ← U ∖ {vi}
19 CLIQUE(U ∩ N(vi); size + weight(vi))
20 if found = true then
21 return
22 end
23 end
24 return
25 **FUNCTION NEW()**
26 max ← 0
27 for i ← n downto 1 do
28 found ← false
29 CLIQUE(Si ∩ N(vi), weight(i))
30 c[i] ← max
31 end
32 return
We assume Si represents vertexes that have larger index than i, for example {vi,vi+1,...,vn}. N(vi) means the adjacent vertexes of vi. The global variable max marks the maximum size of clique that we find for now, and the global variable found marks whether we have found a larger clique. The array c[] record the maximum clique size of Si. size records maximum clique size in local recursion。
There are several prune strategies that could avoid useless search, especially, in line 11 and line 15.
You could use the hash table to implement this algorithm.
Upvotes: 2
Reputation: 1351
Find maximum clique is an NP-hard problem. You can find something useful in Clique problem (Wikipedia).
Upvotes: 1