Abstract:
Graph partitioning is a fundamental problem in many scientific contexts. This document describes the capabilities and operation of Chaco-2.0, a software package designed to partition graphs. Chaco-2.0 allows for recursive application of several methods for finding small edge separators in weighted graphs. These methods include inertial, spectral, Kernighan-Lin and multilevel methods in addition to several simpler strategies. Each of these approaches can be used to partition the graph into two, four or eight pieces at each level of recursion. In addition, the Kernighan-Lin method can be used to improve partitions generated by any of the other algorithms. Brief descriptions of these methods are provided, along with references to relevant literature. Chaco-2.0 can also be used to address various graph sequencing problems, and this capability is briefly described. The user interface, input/output formats and appropriate settings for a variety of code parameters are discussed in detail, and some suggestions on algorithm selection are offered.