Indiana University Bloomington

School of Informatics and Computing

Technical Report TR144:
On the Complexity of Partitioning Sparse Matrix Representations

Edward L. Robertson and J. P. Malmquist
(Jan 1984), 10 pages
[BIT 24 (1984), 60--68]
A standard representation of a sparse matrix is a structure where non-zero elements are linked in rows and columns. A general graph structure corresponding to this representation is defined. The problem of partitioning such a graph into fixed size blocks, so that the number of inter-block links is minimized, is shown to be NP-complete.

Available as: