(Prototype of a) MaxCut and BQP Instance Library
Instance Library for the Maximum Cut and the Unconstrained Binary Quadratic Optimization Problem
Instance: G_20, Dataset: HR
MaxCut instances generated by Christoph Helmberg and Franz Rendl (2000) using the machine independent graph generator ``rudy'' written by G. Rinaldi. The precise calls to ``rudy'' can be obtained from the original article.
The first 21 graphs have 800 nodes. More precisely:
G43 to G54 are again constructed using the same types.
Download links: .mc version, .bq version
The first 21 graphs have 800 nodes. More precisely:
- Graphs G1 to G5 are random graphs with unit weights and a density of 6%.
- G6 to G10 are the same graphs with random edge weights from {-1, 1}.
- G11 to G13 are toroidal grids with random edge weights from {-1, 1}.
- G14 to G17 are composed from the union of two (almost maximal) planar graphs with unit weights.
- G18 to G21 are the same graphs with random edge weights from {-1, 1}.
G43 to G54 are again constructed using the same types.
Download links: .mc version, .bq version
| Instance | G_20 |
| |V| | 800 |
| |E| | 4672 |
| dim(Q) | 800 |
| nz(Q>) | 4672 |
| nz(Diag(Q)) | 701 |
| OSV | n/a |
| Eigenvalues (min, max) | -19.7025, 16.3497 |
| Known correspondences | - |
Instance Visualisation
A visualisation of the instance, created with OGDF (click to enlarge).
Edge Weight Plot
A plot showing the frequency of edge weights, for a high-level overview of the edge weight distributions (click to enlarge).
