[問題] Merge nodes (graph theory problem)

[alden (這真是太危險啦)]

Sorry for type in English.

I've recently face a problem when analyzing the data.

I have about 8000 vertexs, with distance d(i,j) between them.
(i.e. might regard as fully-connected graph)

I now, however, want ot merge the vertexs.
To downsize my number of vertexs.

My goal is to merge every 2 vertexs into 1, so the number of total vertexs become 4000.

My optimal criteria is that the Sum( d(i,j) ) between all pairs of merged node is minimal.


The very first impression is using Greedy algorithm, which easily failed.

Is there any good algorithm to attack this problem?
Or it is just NP.
Does max flow-min cut relate to this problem.

Is the problem similar to the idea of seperating the nodes into two clusters and minimize
the distance between the clusters?

Thanks a lot!

--

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 128.220.29.227
推 DJWS:看起來跟minimum-weight perfect-matching有點關係~ :)
推 yoco315:感謝樓上 @@ 學到新東西
推 alden:thx, eactly mw p-matching is what I need!