CODEWITHSUNDEEP
c#algorithmgraph
StuffHappens
StuffHappens

Reputation: 6557

Finding a maximum weight clique in a weighted graph C# implementation

Is there a freely available implementation of finding a maximum weight clique in weighted graph in C#?

Upvotes: 1

Views: 1885

Answers (2)

MinG
MinG

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

pengdu
pengdu

Reputation: 1351

Find maximum clique is an NP-hard problem. You can find something useful in Clique problem (Wikipedia).

Upvotes: 1

Related Questions