PulseExploreJournal ClubDebatesTrendingResearchersJournals
Instagram
HomeExploreJournal ClubTrending
Synapse
⌘+K
Synapse
February 1, 1970Bell System Technical Journal5,321 citations

An Efficient Heuristic Procedure for Partitioning Graphs

View Full Paper
BKBrian W. KernighanSLShang Min Lin

Key Points

  • Develop a fast, effective heuristic procedure to partition graph nodes into fixed-size subsets while minimizing the total cost of cut edges.
  • Formulated a heuristic optimization algorithm designed to iteratively partition arbitrary weighted graphs into predefined subset sizes.
  • Applied the partitioning framework to minimize interconnection costs in practical engineering problems, such as electronic circuit board layout.
  • The proposed heuristic effectively discovers optimal or near-optimal graph partitions across arbitrary network topologies.
  • The procedure demonstrates sufficient computational speed and efficiency to solve large-scale graph partitioning problems practically.

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.

Ask AI
Helpful
Bookmark
Share
View Full Paper

Cite This Study

Kernighan et al. (1970) studied this question.

synapsesocial.com/papers/6a09268e15fb758097d25b8ehttps://doi.org/10.1002/j.1538-7305.1970.tb01770.x
Ask AI
Helpful
Bookmark
Share
View Full Paper