將稀疏矩陣分成最小數量的組件

Question

如何將稀疏矩陣分區爲最少連接組件數量，以便每個組件在整個組件中都有一個共同的行或列。我應該使用什麼樣的數據結構來在最短的時間內完成這項任務。我認爲要這樣做，我必須最大限度地增加每個組件中的元素數量，以便在輸入時我保存每行和每列中的元素數量。我排序的列表，然後用最大（分鐘（在行元件，在列的元素）），即行或列，

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-

然後，我會先刪除列1.Then我將不得不更新剩餘陣列被佔用大量的 時間和每個行和列的存儲列表是不可行的，因爲它使用大量的內存。我只需告知最小分區數量，而不是實際分區矩陣。在給定的矩陣中，可以將（row1，row2，row3，colum2-（1,2））作爲分區進行分區。

編輯：或者等價地我們可以把它看作一個有兩個數字相關聯的元素，並且我們輸出最小數量的分區，這樣每個分區都有兩個數字中的一個。

Answer 1

我相信你會找到有關這些演講稿：http://www.cs.indiana.edu/classes/b673/notes/GraphPartitioning.pdf