| 简单规则下Vote Control问题的复杂性分析 |
| |
| 引用本文： | 秦勤,王雪瑞,李建.简单规则下Vote Control问题的复杂性分析[J].湖南科技大学学报(自然科学版),2013,28(1):84-86. |
| |
| 作者姓名： | 秦勤 王雪瑞 李建 |
| |
| 作者单位： | 河南工程学院 计算机学院,河南 郑州 450007 |
| |
| 基金项目： | 河南省科技攻关项目(122102310442) |
| |
| 摘 要： | 给定候选人集合C,投票集合V=(v1,v2,…,vn)和候选人c∈C,是否存在V的子集V′,|V′|≤k,使得c∈r(V＼V′).该问题在不同的得分规则下复杂性是不同的.在plurality规则的基础上证明了Reto规则下Vote Control问题是多项式时间可解的,并给出了k′-approval规则下该问题是NP-Complete的证明.
|
| 关 键 词： | Vote Control问题 复杂性 得分规则 |
The complexity of Vote Control problem under simple rules |
| |
| QIN Qin,WANG Xue-rui,LI Jian.The complexity of Vote Control problem under simple rules[J].Journal of Hunan University of Science & Technology(Natural Science Editon),2013,28(1):84-86. |
| |
| Authors: | QIN Qin WANG Xue-rui LI Jian |
| |
| Institution: | College of Computer Science and Technology, Henan Institute of Engineering,Zhengzhou 450007,China |
| |
| Abstract: | |
| |
| Keywords: | Vote Control problem complexity scoring rule |
|
| 点击此处可从《湖南科技大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《湖南科技大学学报(自然科学版)》下载免费的PDF全文 |
|
