We supply instances for the graph partitioning problem. These instances are a local cache of the original collection used by D.S. Johnson et al. plus instances used by T. N. Bui and B. R. Moon and by Monien.

---

The complete set of instances from:
R. Battiti and A. Bertossi. Greedy, Prohibition, and Reactive Heuristics for Graph-Partitioning
IEEE Transactions on Computers , Vol. 48, Number 4, April 1999, pp.361-385.
PDF proofs: gp.pdf

• instances by Johnson and Bui johnson-bui.tar.gz
• additional instances by Monien monien-graphs.tar.gz .
  The format of each line is:
  [number of vertex] (aa,bb) [number of edges] [index of first connected vertex]...[index of last connected vertex]
  NOTE: (aa,bb) is information that is not needed, the indices start from 1

---

The instances are stored in binary DIMACS format. The binary DIMACS format trades the simplicity of the human-readable DIMACS format (see our tutorial) for space savings. If the edge density of the graph is bigger than ~1.2%, the binary storage is more space efficient. Here you can find a converter between plain DIMACS format and binary DIMACS format.

Our results on the above instances

To render the comparisons of the CPU times as platform independent as possible we refer to the SPEC specifications. The SPECs give a common and standardized measure of the computing power of a processor (see below). Note: if you are interested more in science than in applications, other performance measures (like the number of basic operations of different kinds) may be more appropriate.

You can get the PostScript document with our results on Johnson et al. and Bui-Moon instances or the LaTex version of the above.
Please do let us know if you have recent results on the same instances!

Characteristics of the machines on which we run our algorithms:

( SPEC data obtained from: SPEC Benchmark Results )

GIGA (a fast machine, but far from the state-of-the-art by now)

• Digital AlphaServer 2100 Model 5/250
• CPU: alpha V4.0 386
• CLOCK: 250 MHz
• Configuration: 4 CPU Alpha, 1 GB RAM, 12 GB Hard Disk
• Operating System: OSF/1 vers. 4.0
• Performance: SPECint95 5.96

RTM (a rather old machine that is at your disposal within the InterTool's framework)

• CPU: HP-UX 9000 - Series 700 - 747 i
• CLOCK: 100 MHz
• Configuration: 1 CPU HP, 128 Mb RAM, 2 GB Hard Disk
• Operating System: HP-UX 9000
• Performance: SPECint95 3.27 (approximately, exact model is not listed)