A note on "banks winners in tournaments are difficult to recognize" by G. J. Woeginger

Olivier Hudry

doi:10.1007/s00355-003-0241-y

A note on "banks winners in tournaments are difficult to recognize" by G. J. Woeginger

Olivier Hudry

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

Abstract

Given a tournament T, a Banks winner of T is the first vertex of any maximal (with respect to inclusion) transitive subtournament of T. While Woeginger shows that recognizing whether a given vertex of T is a Banks winner is NP-complete, the computation of a Banks winner of T is polynomial, and more precisely linear with respect to the size of T.

Original language	English
Pages (from-to)	113-114
Number of pages	2
Journal	Social Choice and Welfare
Volume	23
Issue number	1
DOIs	https://doi.org/10.1007/s00355-003-0241-y
Publication status	Published - 1 Jan 2004

Access to Document

10.1007/s00355-003-0241-y

Cite this

@article{a9dd485a18a04fa684a28c0953a218dc,

title = "A note on {"}banks winners in tournaments are difficult to recognize{"} by G. J. Woeginger",

abstract = "Given a tournament T, a Banks winner of T is the first vertex of any maximal (with respect to inclusion) transitive subtournament of T. While Woeginger shows that recognizing whether a given vertex of T is a Banks winner is NP-complete, the computation of a Banks winner of T is polynomial, and more precisely linear with respect to the size of T.",

author = "Olivier Hudry",

year = "2004",

month = jan,

day = "1",

doi = "10.1007/s00355-003-0241-y",

language = "English",

volume = "23",

pages = "113--114",

journal = "Social Choice and Welfare",

issn = "0176-1714",

number = "1",

}

TY - JOUR

T1 - A note on "banks winners in tournaments are difficult to recognize" by G. J. Woeginger

AU - Hudry, Olivier

PY - 2004/1/1

Y1 - 2004/1/1

N2 - Given a tournament T, a Banks winner of T is the first vertex of any maximal (with respect to inclusion) transitive subtournament of T. While Woeginger shows that recognizing whether a given vertex of T is a Banks winner is NP-complete, the computation of a Banks winner of T is polynomial, and more precisely linear with respect to the size of T.

AB - Given a tournament T, a Banks winner of T is the first vertex of any maximal (with respect to inclusion) transitive subtournament of T. While Woeginger shows that recognizing whether a given vertex of T is a Banks winner is NP-complete, the computation of a Banks winner of T is polynomial, and more precisely linear with respect to the size of T.

UR - https://www.scopus.com/pages/publications/3142752536

U2 - 10.1007/s00355-003-0241-y

DO - 10.1007/s00355-003-0241-y

M3 - Article

AN - SCOPUS:3142752536

SN - 0176-1714

VL - 23

SP - 113

EP - 114

JO - Social Choice and Welfare

JF - Social Choice and Welfare

IS - 1

ER -

A note on "banks winners in tournaments are difficult to recognize" by G. J. Woeginger

Abstract

Access to Document

Other files and links

Fingerprint

Cite this