Banks winners in tournaments are difficult to recognize

被引：33

作者：

Woeginger, GJ

机构：

[1] Univ Twente, Dept Math, NL-7500 AE Enschede, Netherlands

[2] Graz Tech Univ, Inst Math, A-8010 Graz, Austria

来源：

SOCIAL CHOICE AND WELFARE | 2003年 / 20卷 / 03期

关键词：

Technical Note; Transitive Subtournament; Banks Winner;

D O I：

10.1007/s003550200197

中图分类号：

F [经济];

学科分类号：

02 ;

摘要：

Given a tournament T, a Banks winner of T is the top vertex of any maximal (with respect to inclusion) transitive subtournament of T. In this technical note, we show that the problem of deciding whether some fixed vertex v is a Banks winner for T is NP-complete.

引用

页码：523 / 528

页数：6

共 8 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2]

BANKS J, 1985, SOC CHOICE WELFARE, V2, P295, DOI DOI 10.1007/BF00649265

[3] COVERING RELATIONS, CLOSEST ORDERINGS AND HAMILTONIAN BYPATHS IN TOURNAMENTS [J].

BANKS, JS ;

BORDES, G ;

LEBRETON, M .

SOCIAL CHOICE AND WELFARE, 1991, 8 (04) :355-363

[4]

Copeland A.H., 1951, A reasonable social welfare function

[5]

Laslier Jean-Francois., 1997, TOURNAMENT SOLUTIONS

[6]

Moon J.W., 1968, TOPICS TOURNAMENTS G

[7]

MOULIN H, 1986, SOC CHOICE WELFARE, V3, P272

[8] CYCLIC TOURNAMENTS AND COOPERATIVE MAJORITY VOTING - A SOLUTION [J].

SCHWARTZ, T .

SOCIAL CHOICE AND WELFARE, 1990, 7 (01) :19-29

← 1 →