摘要
给定候选人集合C,投票集合V=(v1,v2,…,vn)和候选人c∈C,是否存在V的子集V',|V'|≤k,使得c∈r(V\V').该问题在不同的得分规则下复杂性是不同的.在plurality规则的基础上证明了Reto规则下Vote Control问题是多项式时间可解的,并给出了k'-approval规则下该问题是NP-Complete的证明.
Given a set of candidatesC, a profile of partial votesV = （v1 ,v2,…,vn） , and a distinguished candidate c ∈ C, is there a subset V＇, ｜ V＇｜ ≤ k such that c ∈ r（V／V＇）. The complexity of this problem is different under different scoring rules. The vote control problem was proved under Reto rule can be solved in polynomial time based on plurality rule, the NP -Complete proof of vote control problem underk＇ -approval rule was also obtained.
出处
《湖南科技大学学报（自然科学版）》
CAS
北大核心
2013年第1期84-86,共3页
Journal of Hunan University of Science And Technology：Natural Science Edition
基金
河南省科技攻关项目(122102310442)
