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 language | English (US) |
|---|---|
| Pages (from-to) | 34-40 |
| Number of pages | 7 |
| Journal | Journal of the ACM (JACM) |
| Volume | 18 |
| Issue number | 1 |
| DOIs | |
| State | Published - Jan 1 1971 |
| Externally published | Yes |
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