Technical Report TR144:
On the Complexity of Partitioning Sparse Matrix Representations
Edward L. Robertson and J. P. Malmquist
(Jan 1984), 10 pages 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:
-
