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

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

Résumé

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.

langue originale	Anglais
Pages (de - à)	113-114
Nombre de pages	2
journal	Social Choice and Welfare
Volume	23
Numéro de publication	1
Les DOIs	https://doi.org/10.1007/s00355-003-0241-y
état	Publié - 1 janv. 2004

Accès au document

10.1007/s00355-003-0241-y

Autres fichiers et liens

Lien vers la publication dans Scopus

Contient cette citation

@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

Résumé

Accès au document

Autres fichiers et liens

Empreinte digitale

Contient cette citation