A note on ``Bank winners in tournaments are difficult to recognize by G. J. Woeginger

DOI10.1007/S00355-003-0241-YMaRDI QIDQ1767293zbMATH OpenOpenAlexFDO

Authors Olivier Hudry

Publication date 8 March 2005

Published in Social Choice and Welfare (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00355-003-0241-y

zbMATH Keywords

NP-complete

Mathematics Subject Classification ID

Review text

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 \textit{G. J. Woeginger} [ibid. 20, 523--528 (2003; Zbl 1073.05538)] 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\).

Recommendations

• Banks winners in tournaments are difficult to recognize
• A smallest tournament for which the Banks set and the Copeland set are disjoint
• A 16-vertex tournament for which Banks set and Slater set are disjoint
• A computational analysis of the tournament equilibrium set
• A survey on the complexity of tournament solutions

Cited in

(14)

• On the complexity of Slater's problems
• A 16-vertex tournament for which Banks set and Slater set are disjoint
• \(k\)-majority digraphs and the hardness of voting with a constant number of voters
• A smallest tournament for which the Banks set and the Copeland set are disjoint
• Minimal extending sets in tournaments
• Banks winners in tournaments are difficult to recognize
• A survey on the linear ordering problem for weighted or unweighted tournaments
• Studies in Computational Aspects of Voting
• The Computational Complexity of Choice Sets
• Computing and visualizing Banks sets of dominance relations using relation algebra and RelView
• Collective decision making
• Computing the minimal covering set
• A tournament of order 14 with disjoint Banks and Slater sets
• An updated survey on the linear ordering problem for weighted or unweighted tournaments

This page was built for publication: A note on ``Bank winners in tournaments are difficult to recognize by G. J. Woeginger

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1767293)