作者yoco315 (眠月)
站内Prob_Solve
标题[问题] covering problem 的变形
时间Wed Aug 29 13:02:02 2012
我知道 covering problem 是 NP-complete
http://tinyurl.com/2aj7953OB
也知道 bipartite covering problem 是 P
http://tinyurl.com/3wazas
我想问的是：给定一个 bipartite graph G(V1, V2, E)
V1, V2 是 bipartite 的两个 vertex set，
如果我希望在 V1 里面找到一组最小的 set 经过 E 来 cover V2，
请问这个问题有名字吗？请前辈给小弟一些方向或是关键字，多谢 :)
我自己有粗想一下，一开始很直觉反应认为就是 covering problem，
但是因为看到 bipartite covering problem 是 P 以後，
有点好奇这个问题是不是也有机会不用到 NP-complete，
我有查到一个叫做 Constrainted Bipartite Covering Problem，
说限制在 V1 里面最多取 k1，V2 里面最多取 k2，这是 NP-Complete，
我的问题虽然可以转成 CBCP，但又有点不一样，目前还没想法 :(
因为不要求一定要 exactly minimum，
如果没有 P 的话，我就考虑使用 GA 去解了……
再次谢过 :)
--
To iterate is human, to recurse, divine.
递回只应天上有, 凡人该当用回圈. L. Peter Deutsch
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 219.71.72.108
1F：推 FRAXIS:你一开始举的例子的Cover是指cover edge 08/29 19:20
2F：→ FRAXIS:但是你真的要问的问题是cover vertex 08/29 19:20
3F：→ FRAXIS:可以搜寻一下Dominating Set 08/29 19:20
5F：推 DJWS:这问题根本就是set cover problem 请爱用GA 08/29 19:25
6F：→ yoco315:收到! 感谢以上两位! 原来我观念这麽不清楚 @@ 08/29 21:31