Vertex Cover

A collection of graphs used in:
E. I. Asgeirsson and C. Stein (2009). Divide-and-Conquer Approximation Algorithm for Vertex Cover. SIAM Journal on Discrete Mathematics, Vol. 23, Issue 3 (pp. 1261–1280).

graphs.zip

Max Clique Vertices Edges Solution size VCopt
brock200_1.clq 200 14834 196
brock200_2.clq 200 9876 194
brock200_3.clq 200 12048 196
brock200_4.clq 200 13089 196
brock400_1.clq 400 59723 395
brock400_2.clq 400 59786 395
brock400_3.clq 400 59681 395
brock400_4.clq 400 59765 396
brock800_1.clq 800 207505 793
brock800_2.clq 800 208166 793
brock800_3.clq 800 207333 794
brock800_4.clq 800 207643 793
C125.9.clq 125 6963 122
C250.9.clq 250 27984 246
C500.9.clq 500 112332 497
C1000.9.clq 1000 450079 996
C2000.5.clq 2000 999836 1989
C2000.9.clq 2000 1799532 1995
c-fat200-1.clq 200 1534 182
c-fat200-2.clq 200 3235 191
c-fat200-5.clq 200 8473 197
c-fat500-1.clq 500 4459 461
c-fat500-2.clq 500 9139 481
c-fat500-5.clq 500 23191 492
c-fat500-10.clq 500 46627 496
gen200_p0.9_44.clq 200 17910 197
gen200_p0.9_55.clq 200 17910 197
gen400_p0.9_55.clq 400 71820 396
gen400_p0.9_65.clq 400 71820 397
gen400_p0.9_75.clq 400 71820 397
hamming6-2.clq 64 1824 62
hamming6-4.clq 64 704 56
hamming8-2.clq 256 31616 254
hamming8-4.clq 256 20864 248
hamming10-2.clq 1024 518656 1022
hamming10-4.clq 1024 434176 1016
johnson8-2-4.clq 28 210 21
johnson8-4-4.clq 70 1855 65
johnson16-2-4.clq 120 5460 105
johnson32-2-4.clq 496 107880 465
keller4.clq 171 9435 156
keller5.clq 776 225990 745
keller6.clq 3361 4619898 3298
MANN_a9.clq 45 918 42
MANN_a27.clq 378 70551 375
MANN_a45.clq 1035 533115 1032
MANN_a81.clq 3321 5506380 3318
p_hat300-1.clq 300 10933 270
p_hat300-2.clq 300 21928 285
p_hat300-3.clq 300 33390 294
p_hat500-1.clq 500 31569 471
p_hat500-2.clq 500 62946 489
p_hat500-3.clq 500 93800 494
p_hat700-1.clq 700 60999 664
p_hat700-2.clq 700 121728 672
p_hat700-3.clq 700 183010 694
p_hat1000-1.clq 1000 122253 961
p_hat1000-2.clq 1000 244799 974
p_hat1000-3.clq 1000 371746 994
p_hat1500-1.clq 1500 284923 1453
p_hat1500-2.clq 1500 568960 1473
p_hat1500-3.clq 1500 847244 1494
san200_0.7_1.clq 200 13930 196
san200_0.7_2.clq 200 13930 194
san200_0.9_1.clq 200 17910 197
san200_0.9_2.clq 200 17910 196
san200_0.9_3.clq 200 17910 198
san400_0.5_1.clq 400 39900 375
san400_0.7_1.clq 400 55860 391
san400_0.7_2.clq 400 55860 390
san400_0.7_3.clq 400 55860 392
san400_0.9_1.clq 400 71820 398
san1000.clq 1000 250500 963
sanr200_0.7.clq 200 13868 196
sanr200_0.9.clq 200 17863 197
sanr400_0.5.clq 400 39984 393
sanr400_0.7.clq 400 55869 394

Max Clique Complement Vertices Edges Solution size Vcopt
brock200_1.clq 200 5066 187 179
brock200_2.clq 200 10024 193 188
brock200_3.clq 200 7852 190 185
brock200_4.clq 200 6811 189 183
brock400_1.clq 400 20077 382 373
brock400_2.clq 400 20014 383 371
brock400_3.clq 400 20119 383 369
brock400_4.clq 400 20035 386 367
brock800_1.clq 800 112095 785 777
brock800_2.clq 800 111434 787 776
brock800_3.clq 800 112267 786 775
brock800_4.clq 800 111957 784 774
C125.9.clq 125 787 99
C250.9.clq 250 3141 215
C500.9.clq 500 12418 458
C1000.9.clq 1000 49421 952
C2000.5.clq 2000 999164 1988
C2000.9.clq 2000 199468 1948
c-fat200-1.clq 200 18366 188 188
c-fat200-2.clq 200 16665 176 176
c-fat200-5.clq 200 11427 142 142
c-fat500-1.clq 500 120291 486 486
c-fat500-2.clq 500 115611 474 474
c-fat500-5.clq 500 101559 436 436
c-fat500-10.clq 500 78123 374 374
gen200_p0.9_44.clq 200 1990 170
gen200_p0.9_55.clq 200 1990 168
gen400_p0.9_55.clq 400 7980 361
gen400_p0.9_65.clq 400 7980 363
gen400_p0.9_75.clq 400 7980 361
hamming6-2.clq 64 192 32 32
hamming6-4.clq 64 1312 60 60
hamming8-2.clq 256 1024 128 128
hamming8-4.clq 256 11776 240 240
hamming10-2.clq 1024 5120 512 512
hamming10-4.clq 1024 89600 992
johnson8-2-4.clq 28 168 24 24
johnson8-4-4.clq 70 560 56 56
johnson16-2-4.clq 120 1680 112 112
johnson32-2-4.clq 496 14880 480
keller4.clq 171 5100 164 160
keller5.clq 776 74710 761 749
keller6.clq 3361 1026582 3330
MANN_a9.clq 45 72 36 29
MANN_a27.clq 378 702 351 252
MANN_a45.clq 1035 1980 990 690
MANN_a81.clq 3321 6480 3240 2221
p_hat300-1.clq 300 33917 295 292
p_hat300-2.clq 300 22922 285 275
p_hat300-3.clq 300 11460 277 264
p_hat500-1.clq 500 93181 492 491
p_hat500-2.clq 500 61804 473 464
p_hat500-3.clq 500 30950 467
p_hat700-1.clq 700 183651 695
p_hat700-2.clq 700 122922 682
p_hat700-3.clq 700 61640 663
p_hat1000-1.clq 1000 377247 995
p_hat1000-2.clq 1000 254701 975
p_hat1000-3.clq 1000 127754 961
p_hat1500-1.clq 1500 839327 1492
p_hat1500-2.clq 1500 555290 1461
p_hat1500-3.clq 1500 277006 1445
san200_0.7_1.clq 200 5970 185 170
san200_0.7_2.clq 200 5970 188 182
san200_0.9_1.clq 200 1990 149 130
san200_0.9_2.clq 200 1990 167 140
san200_0.9_3.clq 200 1990 170 156
san400_0.5_1.clq 400 39900 394 387
san400_0.7_1.clq 400 23940 380 360
san400_0.7_2.clq 400 23940 384 370
san400_0.7_3.clq 400 23940 387 378
san400_0.9_1.clq 400 7980 353 300
san1000.clq 1000 249000 993 985
sanr200_0.7.clq 200 6032 188 182
sanr200_0.9.clq 200 2037 168
sanr400_0.5.clq 400 39816 390
sanr400_0.7.clq 400 23931 385

Min-Coloring graphs Vertices Edges Solution size VCopt
DSJC1000.1.col 1000 49629 956
DSJC1000.5.col 1000 249826 989
DSJC1000.9.col 1000 449449 996
DSJC125.1.col 125 736 94
DSJC125.5.col 125 3891 118
DSJC125.9.col 125 6961 122
DSJC250.1.col 250 3218 217
DSJC250.5.col 250 15668 242
DSJC250.9.col 250 27897 247
DSJC500.1.col 500 12458 464
DSJC500.5.col 500 62624 489
DSJC500.9.col 500 112437 497
DSJR500.1.col 500 3555 439
DSJR500.1c.col 500 121275 493
DSJR500.5.col 500 58862 496
flat1000_50_0.col 1000 245000 980
flat1000_60_0.col 1000 245830 984
flat1000_76_0.col 1000 246708 987
flat300_20_0.col 300 21375 285
flat300_26_0.col 300 21633 289
flat300_28_0.col 300 21695 290
fpsol2.i.1.col 496 11654 189
fpsol2.i.2.col 451 8691 191
fpsol2.i.3.col 425 8688 188
inithx.i.1.col 864 18707 298
inithx.i.1.col2 864 18707 298
inithx.i.2.col 645 13979 280
inithx.i.3.col 621 13969 261
latin_square_10.col 900 307350 890
le450_15a.col 450 8168 396
le450_15b.col 450 8169 388
le450_15c.col 450 16680 426
le450_15d.col 450 16750 424
le450_25a.col 450 8260 370
le450_25b.col 450 8263 382
le450_25c.col 450 17343 416
le450_25d.col 450 17425 425
le450_5a.col 450 5714 393
le450_5b.col 450 5734 393
le450_5c.col 450 9803 409
le450_5d.col 450 9757 411
mulsol.i.1.col 197 3925 97
mulsol.i.2.col 188 3885 98
mulsol.i.3.col 184 3916 99
mulsol.i.4.col 185 3946 100
mulsol.i.5.col 186 3973 98
R1000.1.col 1000 14378 933
R1000.1c.col 1000 485090 988
R1000.5.col 1000 238267 996
R125.1.col 125 209 76
R125.1c.col 125 7501 123
R125.5.col 125 3838 121
R250.1.col 250 867 190
R250.1c.col 250 30227 246
R250.5.col 250 14849 246
school1.col 385 19095 358
school1_nsh.col 352 14612 325
zeroin.i.1.col 211 4100 91
zeroin.i.2.col 211 3541 84
zeroin.i.3.col 206 3540 83

Min-Coloring Graph Complement Vertices Edges Solution size VCopt
DSJC1000.1.col 1000 449871 997
DSJC1000.5.col 1000 249674 990
DSJC1000.9.col 1000 50051 951
DSJC125.1.col 125 7014 123
DSJC125.5.col 125 3859 119
DSJC125.9.col 125 789 96
DSJC250.1.col 250 27907 247
DSJC250.5.col 250 15457 242
DSJC250.9.col 250 3228 217
DSJC500.1.col 500 112292 496
DSJC500.5.col 500 62126 491
DSJC500.9.col 500 12313 458
DSJR500.1.col 500 121195 491
DSJR500.1c.col 500 3475 438
DSJR500.5.col 500 65888 404
flat1000_50_0.col 1000 254500 990
flat1000_60_0.col 1000 253670 989
flat1000_76_0.col 1000 252792 989
flat300_20_0.col 300 23475 293
flat300_26_0.col 300 23217 290
flat300_28_0.col 300 23155 292
fpsol2.i.1.col 496 111106 446
fpsol2.i.2.col 451 92784 431
fpsol2.i.3.col 425 81412 424
inithx.i.1.col 864 354109 863
inithx.i.1.col2 864 354109 863
inithx.i.2.col 645 193711 617
inithx.i.3.col 621 178541 593
latin_square_10.col 900 97200 810
le450_15a.col 450 92857 445
le450_15b.col 450 92856 444
le450_15c.col 450 84345 444
le450_15d.col 450 84275 445
le450_25a.col 450 92765 425
le450_25b.col 450 92762 443
le450_25c.col 450 83682 442
le450_25d.col 450 83600 425
le450_5a.col 450 95311 446
le450_5b.col 450 95291 447
le450_5c.col 450 91222 446
le450_5d.col 450 91268 446
mulsol.i.1.col 197 15381 196
mulsol.i.2.col 188 13693 164
mulsol.i.3.col 184 12920 160
mulsol.i.4.col 185 13074 161
mulsol.i.5.col 186 13232 162
R1000.1.col 1000 485122 988
R1000.1c.col 1000 14410 935
R1000.5.col 1000 261233 808
R125.1.col 125 7541 121
R125.1c.col 125 249 80
R125.5.col 125 3912 95
R250.1.col 250 30258 244
R250.1c.col 250 898 195
R250.5.col 250 16276 198
school1.col 385 54825 377
school1_nsh.col 352 47164 338
zeroin.i.1.col 211 18055 171
zeroin.i.2.col 211 18614 185
zeroin.i.3.col 206 17575 180

Sanchis Vertices Edges Solution size VCopt
graph00.vc 500 2000 250
graph01.vc 500 5000 250
graph02.vc 500 10000 250
graph03.vc 500 20000 250
graph04.vc 500 30000 250
graph05.vc 500 40000 250
graph06.vc 500 50000 250
graph07.vc 500 60000 250
graph09.vc 500 2000 38
graph10.vc 500 5000 385
graph11.vc 500 10000 444
graph12.vc 500 20000 473
graph13.vc 500 30000 439
graph14.vc 500 40000 480
graph15.vc 500 50000 487
graph16.vc 500 60000 443
graph17.vc 500 70000 375
graph18.vc 500 80000 375
graph19.vc 500 90000 375
graph20.vc 500 2000 337
graph21.vc 500 5000 413
graph22.vc 500 10000 454
graph23.vc 500 20000 475
graph24.vc 500 30000 482
graph25.vc 500 40000 487
graph26.vc 500 50000 489
graph27.vc 500 60000 491
graph28.vc 500 70000 492
graph29.vc 500 80000 450
graph30.vc 500 90000 495
graph31.vc 500 100000 450
graph32.vc 500 110000 450

Sanchis complement Vertices Edges Solution size VCopt
graph00.vc 500 122750 498
graph01.vc 500 119750 498
graph02.vc 500 114750 498
graph03.vc 500 104750 498
graph04.vc 500 94750 498
graph05.vc 500 84750 498
graph06.vc 500 74750 498
graph07.vc 500 64750 498
graph09.vc 500 122750 498
graph10.vc 500 119750 498
graph11.vc 500 114750 498
graph12.vc 500 104750 496
graph13.vc 500 94750 496
graph14.vc 500 84750 496
graph15.vc 500 74750 496
graph16.vc 500 64750 496
graph17.vc 500 54750 496
graph18.vc 500 44750 496
graph19.vc 500 34750 496
graph20.vc 500 122750 498
graph21.vc 500 119750 497
graph22.vc 500 114750 497
graph23.vc 500 104750 497
graph24.vc 500 94750 494
graph25.vc 500 84750 494
graph26.vc 500 74750 493
graph27.vc 500 64750 492
graph28.vc 500 54750 492
graph29.vc 500 44750 490
graph30.vc 500 34750 490
graph31.vc 500 24750 490
graph32.vc 500 14750 490

sh2 Vertices Edges Solution size VCopt
sh2-10.dim.sh 839 221844 827
sh2-3.dim.sh 839 345681 836

machine Vertices Edges Solution size VCopt
r100.5 100 2508 95
r200.5 200 10036 191
r300.5 300 22361 292
r400.5 400 40061 392
r500.5 500 62161 491

machine complement Vertices Edges Solution size VCopt
r100.5 100 2442 93
r200.5 200 9864 193
r300.5 300 22489 293
r400.5 400 39739 393
r500.5 500 62589 491

benchmarksuite Vertices Edges Solution size VCopt
vtx_cov_1.gph 100 200 54 53
vtx_cov_2.gph 100 200 52 50
vtx_cov_3.gph 100 200 56 55
vtx_cov_4.gph 100 200 56 54

benchmarksuite complement Vertices Edges Solution size VCopt
vtx_cov_1.gph 100 4750 97
vtx_cov_2.gph 100 4750 97
vtx_cov_3.gph 100 4750 98
vtx_cov_4.gph 100 4750 98

Contact info

School of Science and Engineering
Reykjavík University
Menntavegur 1
101 Reykjavík, Iceland
(+354) 599 6385
eyjo@ru.is