On the Complexity of Partitioning Sparse Matrix Representations

(Jan 1984), 10 pages

[BIT 24 (1984), 60--68]

**Abstract:**-
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:**

- PDF (23 KBytes)
- Compressed PostScript (23 KBytes)
- PostScript (via FTP download)