Bruce Hendrickson
ABSTRACT
The graph partitioning problem is that of dividing the vertices of a graph into sets of specified sizes such that few edges cross between sets. This NP-complete problem arises in many important scientific and engineering problems. Prominent examples include the decomposition of data structures for parallel computation, the placement of circuit elements and the ordering of sparse matrix computations. We present a multilevel algorithm for graph partitioning in which the graph is approximated by a sequence of increasingly smaller graphs. The smallest graph is then partitioned using a spectral method, and this partition is propagated back through the hierarchy of graphs. A variant of the Kernighan-Lin algorithm is applied periodically to refine the partition. The entire algorithm can be implemented to execute in time proportional to the size of the original graph. Experiments indicate that, relative to other advanced methods, the multilevel algorithm produces high quality partitions at low cost.
- 1.S. T. BARNARD AND H. D. SIMON, A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems, in Proc. 6th SIAM Conf. Parallel Processing for Scientific Computing, SIAM, 1993, pp. 711-718.Google Scholar
- 2.T. BUI AND C. JONES, A heuristic for reducing fill in sparse matrix factorization, in Proc. 6th SIAM Conf. Parallel Processing for Scientific Computing, SIAM, 1993, pp. 445-452.Google Scholar
- 3.P. DINIZ, S. PLIMPTON, B. HENDRICKSON, AND R. LELAND, Parallel algorithms for dynamically partitioning unstructured grids, in Proc. 7th SIAM Conf. Parallel Processing for Scientific Computing, SIAM, 1995, pp. 615-620.Google Scholar
- 4.A. E. DUNLOP AND B. W. KERNIGHAN, A procedure for placement of standard-cell VLSI circuits, IEEE Trans. CAD, CAD-4 (1985), pp. 92-98.Google Scholar
- 5.C. M. FIDUCCIA AND R. M. MATTHEYSES, A linear time heuristic for improving network partitions, in Proc. 19th IEEE Design Automation Conference, IEEE, 1982, pp. 175-181. Google ScholarDigital Library
- 6.M. GAREY, D. JOHNSON, AND L. STOCKMEYER, Some simplified NP-complete graph problems, Theoretical Computer Science, 1 (1976), pp. 237-267.Google ScholarCross Ref
- 7.J. R. GILBERT AND E. ZMIJEWSKI, A parallel graph partitioning algorithm for a message-passing multiprocessor, Intl. J. Parallel Programming, 16 (1987), pp. 498-513. Google ScholarDigital Library
- 8.S. HAMMOND. Personal Communication, November 1992. Available through anonymous ftp at riacs.edu, file /pub/grids/3elt.grid.Google Scholar
- 9.S. HAMMOND, Mapping unstructured grid computations to massively parallel computers, PhD thesis, Rensselaer Polytechnic Institute, Dept. of Computer Science, Troy, NY, 1992. Google ScholarDigital Library
- 10.B. HENDRICKSON AND R. LELAND, An improved spectral load balancing method, in Proc. 6th SIAM Conf. Parallel Processing for Scientific Computing, SIAM, March 1993, pp. 953-961.Google Scholar
- 11.B. HENDRICKSON AND R. LELAND, Multidimensional spectral load balancing, Tech. Rep. SAND93-0074, Sandia National Laboratories, Albuquerque, NM, January 1993.Google ScholarCross Ref
- 12.B. HENDRICKSON AND R. LELAND, The Chaco user's guide, version 2.0, Tech. Rep. SAND94-2692, Sandia National Laboratories, Albuquerque, NM, October 1994.Google Scholar
- 13.B. HENDRICKSON AND R. LELAND, An improved spectral graph partitioning algorithm for mapping parallel computations, SIAM J. Sci. Comput., 16 (1995). Google ScholarDigital Library
- 14.B. HENDRICKSON, R. LELAND, AND R. VAN DRIESSCHE, Enhancing data locality by using terminal propagation, in Proc. 29th Hawaii Conf. System Sciences, January 1996. To appear. Google ScholarDigital Library
- 15.C. A. JONES, Vertex and Edge Partitions of Graphs, PhD thesis, Penn State, Dept. Computer Science, State College, PA, 1992. Google ScholarDigital Library
- 16.G. KARYPIS AND V. KUMAR, A fast and high quality multilevel scheme for partitioning irregular graphs, Tech. Rep. CORR 95-035, University of Minnesota, Dept. Computer Science, Minneapolis, MN, June 1995.Google Scholar
- 17.B. KERNIGHAN AND S. LIN, An efficient heuristic procedure for partitioning graphs, Bell System Technical Journal, 29 (1970), pp. 291-307.Google ScholarCross Ref
- 18.R. PONNUSAMY, N. MANSOUR, A. CHOUDHARY, AND G. C. FOX, Graph contraction and physical optimization methods: a quality-cost tradeoff for mapping data on parallel computers, in Intl. Conf. Supercomputing, Tokyo, Japan, July 1993. Google ScholarDigital Library
- 19.A. POTHEN, H. SIMON, AND K. LIOU, Partitioning sparse matrices with eigenvectors of graphs, SIAM J. Matrix Anal., 11 (1990), pp. 430-452. Google ScholarDigital Library
- 20.J. E. SAVAGE AND M. G. WLOKA, Parallelism in graph-partitioning, J. Par. Dist. Comput., 13 (1991), pp. 257-272.Google ScholarCross Ref
- 21.H. D. SIMON, Partitioning of unstructured problems for parallel processing, in Proc. Conference on Parallel Methods on Large Scale Structural Analysis and Physics Applications, Pergammon Press, 1991.Google Scholar
- 22.P. SUARIS AND G. KEDEM, An algorithm for quadrisection and its application to standard cell placement, IEEE Trans. Circuits and Systems, 35 (1988), pp. 294-303.Google ScholarCross Ref
- 23.J. SWISSHELM. Personal Communication, February 1992.Google Scholar
- 24.D. VANDERSTRAETEN, C. FARHAT, P. S. CHEN, R. KEUNINGS, AND O. ZONE, A retrofit based methodology for the fast generation and optimization of mesh partitions: beyond the minimum interface size criteria, Comput. Meths. Appl. Mech. Eng., (1995). To appear.Google Scholar
- 25.D. VANDERSTRAETEN, R. KEUNINGS, AND C. FARHAT, Optimization of mesh partitions and impact on parallel CFD, in Parallel Computational Fluid Dynamics, New Trends and Advances, A. Ecer, J. Hauser, P. Leca, and J. Periaux, eds., Elsevier, 1995, pp. 233-239. (Also in Proc. Parallel CFD '93).Google Scholar
- 26.C. WALSHAW, M. CROSS, AND M. EVERETT, A parallelisable algorithm for optimising unstructured mesh partitions, Tech. Rep. 95/IM/03, University of Greenwich, London SE18 6PF, UK, 1995. (submitted for publication).Google Scholar
- 27.R. WILLIAMS, Performance of dynamic load balancing algorithms for unstructured mesh calculations, Concurrency, 3 (1991), pp. 457-481. Google ScholarDigital Library
Index Terms
- A multilevel algorithm for partitioning graphs
Recommendations
Partitioning of a graph into induced subgraphs not containing prescribed cliques
AbstractLet K p be a complete graph of order p ≥ 2. A K p-free k-coloring of a graph H is a partition of V ( H ) into V 1 , V 2 … , V k such that H [ V i ] does not contain K p for each i ≤ k. In 1977 Borodin and Kostochka conjectured that any graph H ...
Multilevelk-way Partitioning Scheme for Irregular Graphs
In this paper, we present and study a class of graph partitioning algorithms that reduces the size of the graph by collapsing vertices and edges, we find ak-way partitioning of the smaller graph, and then we uncoarsen and refine it to construct ak-way ...
Partitioning graphs into generalized dominating sets
We study the computational complexity of partitioning the vertices of a graph into generalized dominating sets. Generalized dominating sets are parameterized by two sets of nonnegative integers σ and ρ which constrain the neighborhood N(υ) of vertices. ...
Comments