An Efficient Heuristic Procedure for Partitioning Graphs

1.1 Definition of the Problem This paper deals with the following combinatorial problem: given a graph G with costs on its edges, partition the nodes of G into subsets no larger than a given maximum size, so as to minimize the total cost of the edges cut. One important practical example of this problem is placing the components of an electronic circuit onto printed circuit cards or substrates, so as to minimize the number of connections between cards. The components are the nodes of the graph, and the circuit connections are the edges. There is some maximum number of components which may be placed on any card. Since connections between cards have high cost compared to connections within a board, the object is to minimize the number of interconnections between cards. This partitioning problem also arises naturally in an attempt to improve the paging properties of programs for use in computers with paged memory organization. A program (at least statically) can be thought of as a set of connected entities. The entities might be subroutines, or procedure blocks, or single instruction and data items, depending on viewpoint and the level of detail required. The connections 291