 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
应该把某些npc团数问题规约到这个问题才能证明npc吧?In Reply To:感觉像NP-Complete... Posted by:frkstyc at 2006-10-27 22:18:14 > 构一个新图G'，边(a,b)存在当且仅当G中comm(a,b)<maxComm/4。求C相当于在G'中将顶点集划分成最 > 多k个团。|C|<=k，所以至少有一个团的大小大于等于n/k。假如这个问题是P问题，那么某些团数问题就是 > P问题了，离证明NPC还缺一点点…… > Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
