Instance: G_54, 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:
  • 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}.
The next 21 graphs, G22 to G42, have the analogous types but with 2000 nodes.
G43 to G54 are again constructed using the same types.

Download links: .mc version, .bq version
Instance G_54
|V| 1000
|E| 5916
dim(Q) 1000
nz(Q>) 5916
nz(Diag(Q)) 1000
OSV n/a
Eigenvalues (min, max) -137.28, -5.20733e-14
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).

Website © 2021-2024 by Sven Mallach. All rights reserved. Imprint.