作者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