[問題] Merge nodes (graph theory problem)
看板Prob_Solve (計算數學 Problem Solving)作者alden (這真是太危險啦)時間17年前 (2007/10/20 01:13)推噓3(3推 0噓 0→)留言3則, 3人參與討論串1/1
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
推
10/20 21:52, , 1F
10/20 21:52, 1F
推
10/21 09:53, , 2F
10/21 09:53, 2F
推
10/23 03:13, , 3F
10/23 03:13, 3F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-4
30