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