- Converter: convert from benchmarks from
asciitobinaryformat and vice versa.
From Ke Xu’s website http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm
| File | Vertices | Max IS[fn:1] | 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 |
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.
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 |
- 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)
Back to benchmark instances page
[fn:1] IS: indepdent set