Banks winners in tournaments are difficult to recognize

Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

46 Citations (Scopus)

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 languageEnglish
Pages (from-to)523-528
Number of pages6
JournalSocial choice and welfare
Volume20
Issue number3
DOIs
Publication statusPublished - 2003

Keywords

  • IR-58670
  • METIS-213302

Fingerprint Dive into the research topics of 'Banks winners in tournaments are difficult to recognize'. Together they form a unique fingerprint.

Cite this