On the complexity of Slater's problems
AbstractGiven 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.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoArticle provided by Elsevier in its journal European Journal of Operational Research.
Volume (Year): 203 (2010)
Issue (Month): 1 (May)
Contact details of provider:
Web page: http://www.elsevier.com/locate/eor
Complexity Tournament solutions Slater solution Majority tournament;
You can help add them by filling out this form.
CitEc Project, subscribe to its RSS feed for this item.
- Olivier Hudry & Bernard Monjardet, 2010.
"Consensus theories : An oriented survey,"
Documents de travail du Centre d'Economie de la Sorbonne
10057, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
- Hudry, Olivier, 2012. "On the computation of median linear orders, of median complete preorders and of median weak orders," Mathematical Social Sciences, Elsevier, vol. 64(1), pages 2-10.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Zhang, Lei).
If references are entirely missing, you can add them using this form.