Yan Jin, Jin-Kao Hao*. "General swap-based multiple neighborhood tabu search for the maximum independent set problem". Engineering Applications of Artificial Intelligence 37: 20-33, 2015.

Table1. Detailed computational results of SBLS on the set of 21 difficult DIMACS and BHOSLIB instances and 11 CODE instances. 

No. Graph Size* Optimal Solution
1 brock400_1 27 Click here
2 brock400_2 29 Click here
3 brock400_3 31 Click here
4 brock400_4 33 Click here
5 brock800_1 23 Click here
6 brock800_2 24 Click here
7 brock800_3 25 Click here
8 brock800_4 26 Click here
9 C2000.9 80 Click here
10 C4000.5 18 Click here
11 frb30-15-1 30 Click here
12 frb35-17-1 35 Click here
13 frb40-19-1 40 Click here
14 frb45-21-1 45 Click here
15 frb50-23-1 50 Click here
16 frb53-24-1 53 Click here
17 frb56-25-1 56 Click here
18 frb59-26-1 59 Click here
19 frb100-40 97 Click here
20 MANN_a45 345 Click here
21 MANN_a81 1100 Click here
22 1dc.1024 94 Click here
23 1dc.2048 172 Click here
24 2dc.1024 16 Click here
25 2dc.2048 24 Click here
26 1et.1024 171 Click here
27 1et.2048 316 Click here
28 1tc.1024 196 Click here
29 1tc.2048 352 Click here
30 1zc.1024 112 Click here
31 1zc.2048 198 Click here
32 1zc.4096 379 Click here

 

Notes:

1. DIMACS graphs are available on-line from http://www.cs.hbg.psu.edu/txn131/clique.html, BHOSLIB benchmark is available from http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.html and CODE benchmark is available from http://neilsloane.com/doc/graphs.html or can be provided on request to jin@info.univ-angers.fr or jinyan.hust@gmail.com.

2. Program Code is available here or can be provided on request to hao@info.univ-angers.fr or jinyan.hust@gmail.com.

3. Given a graph G = (V, E), the format of the Maximum Independent Set S is as follows:

   v1 v2 ... vn

where vi (i=1,...,n) is the ith vertex which is included in S (vi ∈ {0,1,2,...,|V|-1}) and n is the cardinality of S.