An Efficient Heuristic Procedure for Partitioning Graphs

Research output: Contribution to journalArticle

3130 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)291-307
Number of pages17
JournalBell System Technical Journal
Volume49
Issue number2
DOIs
StatePublished - Feb 1970

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'An Efficient Heuristic Procedure for Partitioning Graphs'. Together they form a unique fingerprint.

Cite this