On the complexity of Slater's problems
Given a tournament T, Slater's problem consists in determining a linear order (i.e. a complete directed graph without directed cycles) at minimum distance from T, the distance between T and a linear order O being the number of directed edges with different orientations in T and in O. This paper studies the complexity of this problem and of several variants of it: computing a Slater order, computing a Slater winner, checking that a given vertex is a Slater winner and so on.
References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Pierre Barthelemy, Jean & Monjardet, Bernard, 1981. "The median procedure in cluster analysis and social choice theory," Mathematical Social Sciences, Elsevier, vol. 1(3), pages 235-267, May.
- Gerhard J. Woeginger, 2003. "Banks winners in tournaments are difficult to recognize," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 20(3), pages 523-528, 06.
- Olivier Hudry, 2004. "A note on “Banks winners in tournaments are difficult to recognize” by G. J. Woeginger," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 23(1), pages 113-114, 08.
- Hudry, Olivier, 2009. "A survey on the complexity of tournament solutions," Mathematical Social Sciences, Elsevier, vol. 57(3), pages 292-303, May.
When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:203:y:2010:i:1:p:216-221. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Shamier, Wendy)
If references are entirely missing, you can add them using this form.