将稀疏矩阵划分为最小数量的组件

Question

如何将稀疏矩阵划分为最少数量的连接组件，以便每个组件在整个组件中都有一个公共行或列。为了在最短的时间内完成这项任务，我应该使用什么数据结构。我想，要做到这一点，我必须最大化每个组件中的元素数量，以便在接受输入时，在每行和每列中存储元素的数量。我对列表进行排序，然后使用max(min(行中的元素，列中的元素)对行或列进行排序)，即，

   row 5-1   column 4-2
   row 4-1   column 3-2
   row 3-2   column 2-3
   row 2-2   column 1-3
   row 1-10

对于矩阵：

 x
 x
x x
x  x
xxxxxxxxxx 

(x表示非零位置)(此矩阵的最终输出应为4)

其中左下角是1,1

然后我将首先删除第一列，然后我将不得不更新剩余的数组，这会占用很多时间，而且存储每行和每列的列表也是不可行的，因为它使用了大量的内存。我只需要告诉最小分区数，而不是对矩阵进行实际分区。在给定的矩阵中，可以用(row1，row2，row3，colum2-(1,2))作为划分。

EDIT:或者等效地，我们可以认为这是一个集合a元素，它有两个与之关联的数字，我们输出最小数量的分区，使得每个分区都有两个数字中的一个是公共的。

Answer 1

我相信你会发现这些演讲幻灯片是相关的：http://www.cs.indiana.edu/classes/b673/notes/GraphPartitioning.pdf