The Node Capacitated Graph Partitioning Problem - Benchmark Instances

Authors:

C. E. Ferreira, A. Martin, C. C. de Souza, R. Weismantel, and L. A. Wolsey

The benchmark

Here you find the instances used in the paper "The Node Capacitated Graph Partitioning Problem: A Computational Study" (Mathematical Programming, series B, 81, 229--256, 1998) by C. E. Ferreira, A. Martin, C. C. de Souza, R. Weismantel and L. A. Wolsey (see also the companion paper "The Node Capacitated Graph Partitioning Problem: Formulations and Valid Inequalities", Mathematical Programming, series A, 74 , 247-266, 1996, by the same authors).

These instances were made available by the authors to help other researchers to test their own algorithms for graph partition problems and are intended to be used solely for scientific purposes. Notice that there are more instances in this benchmarks than those appearing in the original paper.

The entire dataset can be downloaded here. Use the README file to check the instance format.

Citing this page:

    Use the BibTeX entry:

    @Misc{graph-partition-benchmark-page,
     author = {C. E. Ferreira, A. Martin, C. C. de Souza, R. Weismantel and L. A. Wolsey},
     title = {The Node Capacitated Graph Partitioning Problem -- Benchmark Instances},
     year = {2011},
     note = {\sl{www.ic.unicamp.br/$\sim$cid/Problem-instances/Graph-Partition}}
    }

Contact Address

Cid C. de Souza
Universidade Estadual de Campinas
Instituto de Computação
Avenida Albert Einstein, 1251
13083-852 Campinas, SP, Brasil
Phone: +55 19 3521.5877
Fax: +55 19 3521.5847
e-mail: