Optimal Sequential Partitions of Graphs

Research output: Contribution to journalArticlepeer-review

65 Scopus citations


This paper presents an algorithm for finding a minimum cost partition of the nodes of a graph into subsets of a given size, subject to the constraint that the sequence of the nodes may not be changed, that is, that the nodes in a subset must have consecutive numbers. The running time of the procedure is proportional to the number of edges in the graph. One possible application of this algorithm is in partitioning computer programs into pages for operation in a paging machine. The partitioning minimizes the number of transitions between pages.

Original languageEnglish (US)
Pages (from-to)34-40
Number of pages7
JournalJournal of the ACM (JACM)
Issue number1
StatePublished - Jan 1 1971
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


  • graph partitioning
  • graph theory
  • pagination
  • partitioning
  • segmentation


Dive into the research topics of 'Optimal Sequential Partitions of Graphs'. Together they form a unique fingerprint.

Cite this