Abstract
We consider the problem of partitioning the nodes of a graph with costs on its edges into subsets of given sizes so as to minimize the sum of the costs on all edges cut. This problem arises in several physical situations — for example, in assigning the components of electronic circuits to circuit boards to minimize the number of connections between boards. This paper presents a heuristic method for partitioning arbitrary graphs which is both effective in finding optimal partitions, and fast enough to be practical in solving large problems.
Keywords
HeuristicGraph partitionGraphComputer scienceMathematical optimizationElectronic circuitMathematicsAlgorithmTheoretical computer scienceEngineering
Related Publications
An efficient eigenvector approach for finding netlist partitions
A fast eigenvector technique for obtaining good initial node partitions of netlists for use in interchange heuristics is described. The method is based on approximating the netl...
New spectral methods for ratio cut partitioning and clustering
Partitioning of circuit netlists in VLSI design is considered. It is shown that the second smallest eigenvalue of a matrix derived from the netlist gives a provably good approxi...
Spectral partitioning works: planar graphs and finite element meshes
Spectral partitioning methods use the Fiedler vector-the eigenvector of the second-smallest eigenvalue of the Laplacian matrix-to find a small separator of a graph. These method...
Lower Bounds for the Partitioning of Graphs
Let a k-partition of a graph be a division of the vertices into k disjoint subsets containing m <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.or...
Local Graph Partitioning using PageRank Vectors
A local graph partitioning algorithm finds a cut near a specified starting vertex, with a running time that depends largely on the size of the small side of the cut, rather than...
Publication Info
- Year
- 1970
- Type
- article
- Volume
- 49
- Issue
- 2
- Pages
- 291-307
- Citations
- 5205
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
5205
OpenAlex
Cite This
Brian W. Kernighan,
Shang Min Lin
(1970).
An Efficient Heuristic Procedure for Partitioning Graphs.
Bell System Technical Journal
, 49
(2)
, 291-307.
https://doi.org/10.1002/j.1538-7305.1970.tb01770.x
Identifiers
- DOI
- 10.1002/j.1538-7305.1970.tb01770.x