作者sayitagain ()
看板Prob_Solve
標題[問題] Graph mining
時間Fri Jan 6 16:24:22 2012
假設今天給定一個graph G=(V,E)
edge 與 node上面都有weighting
如果我今天要找k個點
讓這k個點之間的edge + node最大
有沒有什麼現有的演算法呢
謝謝
--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.42.22
1F：→ suhorng:請問之間的edge是指什麼? 至少其中一端點是這k個點的邊嗎? 01/06 17:28
2F：推 flere:可以把node拆開成兩個,中間補上node的weight當成邊 01/07 11:12
3F：→ flere:我想這個圖應該是DAG啦,如果是的話做DP最長路徑即可 01/07 11:13
4F：→ flere:是說我也跟一樓有一樣的困惑....你點全部找的話不就醫定會 01/07 11:14
5F：→ flere:大嗎?是不是你限制還是題意沒說清楚呀?? 01/07 11:14
6F：→ sayitagain:edge的兩個端點都是k個點之中的 其實就是DkS的問題 01/11 12:46
7F：→ sayitagain:但是要加上node也有weighting 01/11 12:46
8F：→ sayitagain:flere大的問題 我想應該是我忘了說有n個node 01/11 12:47
9F：→ sayitagain:暴力法就是C(n,k) 但是不想用暴力QQ 謝謝 01/11 12:48
10F：推 DJWS:我用谷割搜尋DkS problem 有找到投影片說這是NP-hard 01/11 22:13
11F：→ DJWS:所以您需要的是近似演算法 還是特殊圖的演算法呢？ 01/11 22:14
12F：→ sayitagain:謝謝熱心的D大 我想知道有沒有approximation 01/13 09:20
13F：推 DJWS:有耶 我用谷歌搜尋DkS problem approximation 有一份投影片 01/13 11:06
14F：→ DJWS:上面列的滿詳細的 不過我都看不懂就是了... 01/13 11:07
16F：→ sayitagain:感謝! 02/21 22:15