Optimal Sequential Partitions of Graphs

Research output: Contribution to journalArticle

56 Scopus citations

Abstract

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)
Volume18
Issue number1
DOIs
StatePublished - Jan 1 1971

All Science Journal Classification (ASJC) codes

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

Keywords

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

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

  • Cite this