[問題] Graph mining

[sayitagain ()]

假設今天給定一個graph G=(V,E)

edge 與 node上面都有weighting

如果我今天要找k個點

讓這k個點之間的edge + node最大

有沒有什麼現有的演算法呢

謝謝

--

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.42.22
→ suhorng:請問之間的edge是指什麼? 至少其中一端點是這k個點的邊嗎?
推 flere:可以把node拆開成兩個,中間補上node的weight當成邊
→ flere:我想這個圖應該是DAG啦,如果是的話做DP最長路徑即可
→ flere:是說我也跟一樓有一樣的困惑....你點全部找的話不就醫定會
→ flere:大嗎?是不是你限制還是題意沒說清楚呀??
→ sayitagain:edge的兩個端點都是k個點之中的   其實就是DkS的問題
→ sayitagain:但是要加上node也有weighting
→ sayitagain:flere大的問題  我想應該是我忘了說有n個node
→ sayitagain:暴力法就是C(n,k)  但是不想用暴力QQ  謝謝
推 DJWS:我用谷割搜尋DkS problem　有找到投影片說這是NP-hard
→ DJWS:所以您需要的是近似演算法　還是特殊圖的演算法呢？
→ sayitagain:謝謝熱心的D大  我想知道有沒有approximation
推 DJWS:有耶 我用谷歌搜尋DkS problem approximation  有一份投影片
→ DJWS:上面列的滿詳細的  不過我都看不懂就是了...
→ DJWS:http://cgi.di.uoa.gr/~mliazi/Papers/APPOL.pdf
→ sayitagain:感謝!