The Chaco user`s guide. Version 1.0
Sandia National Labs., Albuquerque, NM (United States), B. Hendrickson, USDOE, Washington, DC (United States) et al. · 1993
Graph partitioning is a fundamental problem in many scientific settings. This document describes the capabilities and operation of Chaco, a software package designed to partition graphs. Chaco allows for recursive application of any of several different 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 methods 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 methods. Brief descriptions of these methods are provided, along with references to relevant literature. 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.
Cited by 655 works. doi:10.2172/10106339 Open-access PDF
Authors
- Sandia National Labs., Albuquerque, NM (United States)
- B. Hendrickson
- USDOE, Washington, DC (United States)
References
- Matrix Computations
- An Efficient Heuristic Procedure for Partitioning Graphs
- Partitioning Sparse Matrices with Eigenvectors of Graphs
- Partitioning of unstructured problems for parallel processing
- An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
- Improving the performance of the Kernighan-Lin and simulated annealing graph bisection algorithms
- An algorithm for quadrisection and its application to standard cell placement
- Mapping unstructured grid computations to massively parallel computers