A note on the query complexity of the Condorcet winner problem

DOI10.1016/J.IPL.2008.07.012zbMATH Open1191.68899OpenAlexW2019927599MaRDI QIDQ975500FDOQ975500

Authors: Ariel D. Procaccia 

Publication date: 9 June 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.07.012

Recommendations

• A survey on the complexity of tournament solutions
• Tournament games and Condorcet voting
• Computing with voting trees
• Condorcet winning sets
• How hard is it to tell which is a Condorcet committee?

zbMATH Keywords

analysis of algorithmsgraph algorithmstheory of computationsocial choiceconcrete complexity

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

Cites Work

• Title not available (Why is that?)
• On recognizing graph properties from adjacency matrices
• A topological approach to evasiveness
• Sorting, Minimal Feedback Sets, and Hamilton Paths in Tournaments

Cited In (5)

• Reducing the time required to find the Kemeny ranking by exploiting a necessary condition for being a winner
• Single-Elimination Brackets Fail to Approximate Copeland Winner.
• Condorcet winner configurations of linear networks
• Beyond the worst case: semi-random complexity analysis of winner determination
• Query complexity of tournament solutions

This page was built for publication: A note on the query complexity of the Condorcet winner problem

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