Banks winners in tournaments are difficult to recognize

Gerhard Woeginger

doi:10.1007/s003550200197

Banks winners in tournaments are difficult to recognize

Gerhard Woeginger

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

51 Citations (Scopus)

6 Downloads (Pure)

Abstract

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.

Original language	English
Pages (from-to)	523-528
Number of pages	6
Journal	Social choice and welfare
Volume	20
Issue number	3
DOIs	https://doi.org/10.1007/s003550200197
Publication status	Published - 2003

Keywords

IR-58670
METIS-213302

Access to Document

10.1007/s003550200197

Cite this

@article{9e410251af60435f8ec718a3e1f6693d,

title = "Banks winners in tournaments are difficult to recognize",

abstract = "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.",

keywords = "IR-58670, METIS-213302",

author = "Gerhard Woeginger",

year = "2003",

doi = "10.1007/s003550200197",

language = "English",

volume = "20",

pages = "523--528",

journal = "Social choice and welfare",

issn = "0176-1714",

publisher = "Springer",

number = "3",

}

TY - JOUR

T1 - Banks winners in tournaments are difficult to recognize

AU - Woeginger, Gerhard

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

KW - IR-58670

KW - METIS-213302

U2 - 10.1007/s003550200197

DO - 10.1007/s003550200197

M3 - Article

SN - 0176-1714

VL - 20

SP - 523

EP - 528

JO - Social choice and welfare

JF - Social choice and welfare

IS - 3

ER -

Banks winners in tournaments are difficult to recognize

Abstract

Keywords

Access to Document

Fingerprint

Cite this