Detail of message

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

感觉像NP-Complete...

Posted by frkstyc at 2006-10-27 22:18:14
In Reply To:Re:还是支持styc的意见,形式化描述一下问题吧.可能我没理解你的问题,也可能你没理解我的说法 Posted by:guoxi022 at 2006-10-27 21:53:01

构一个新图G'，边(a,b)存在当且仅当G中comm(a,b)<maxComm/4。求C相当于在G'中将顶点集划分成最
多k个团。|C|<=k，所以至少有一个团的大小大于等于n/k。假如这个问题是P问题，那么某些团数问题就是
P问题了，离证明NPC还缺一点点……

> 在图G中，把这样的聚集C找出来，要求|C| <= k，且 C 不包含这样的两个结点，
>   comm(a,b) >= 1/4 maxComm，comm(a,b)是C中任意两个结点之间的距离，maxComm是图中两个最远结点之间的距离。

Followed by:

好像反了?... (145) ArXoR 2006-10-27 22:25:53
- Re:好像反了?... (40) guoxi022 2006-10-28 10:59:27
应该把某些npc团数问题规约到这个问题才能证明npc吧? (145) ArXoR 2006-10-30 18:44:10
- Re:应该把某些npc团数问题规约到这个问题才能证明npc吧? (25) frkstyc 2006-10-30 18:46:16
- 这样行不行: (164) ArXoR 2006-10-30 18:55:35

Post your reply here:

Home Page Go Back To top