Vertex Cover Benchmark Instances
Table of Contents
1 Utils
- Converter: convert from benchmarks from
asciitobinaryformat and vice versa.
2 Vertex Cover instances
From Ke Xu's website http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm
| File | Vertices | Max IS1 | Min VC | |
|---|---|---|---|---|
| 1 | frb30-15-mis (5 instances) | 450 | 30 | 420 |
| 2 | frb35-17-mis (5 instances) | 595 | 35 | 560 |
| 3 | frb40-19-mis (5 instances) | 760 | 40 | 720 |
| 4 | frb45-21-mis (5 instances) | 945 | 45 | 900 |
| 5 | frb50-23-mis (5 instances) | 1150 | 50 | 1100 |
| 6 | frb53-24-mis (5 instances) | 1272 | 53 | 1219 |
| 7 | frb56-25-mis (5 instances) | 1400 | 56 | 1344 |
| 8 | frb59-26-mis (5 instances) | 1534 | 59 | 1475 |
3 Clique complement graphs
From Muthubharathi Periannan's MS thesis at Penn State Harrisburg.
- Clique to Vertex Cover converter: converts graph instances for Max Clique into complement graphs, usable for Min Vertex Covering. The size of the minimum vertex cover is the difference between the total number of vertices and the size of the max clique.
4 Random Graphs
From Muthubharathi Periannan's MS thesis at Penn State Harrisburg.
| File | Vertices | |
|---|---|---|
| 1 | random graphs with 50 vertices - 10 instances | 50 |
| 2 | random graphs with 100 vertices - 10 instances | 100 |
| 3 | random graphs with 200 vertices - 5 instances | 200 |
| 4 | random graphs with 250 vertices - 5 instances | 250 |
| 5 | random graphs with 500 vertices - 5 instances | 500 |
5 Other Instances
- BHOSLIB
- Benchmarks with Hidden Optimum Solutions for Graph Problems (Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring): http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm (link no longer exists)
Footnotes:
1
IS: indepdent set