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 stud...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2010-05, Vol.203 (1), p.216-221
Main Author: Hudry, Olivier
Format: Article
Language:English
Subjects:
Applied sciences
Complexity
Complexity theory
Complexity Tournament solutions Slater solution Majority tournament
Exact sciences and technology
Flows in networks. Combinatorial problems
Majority tournament
Operational research and scientific management
Operational research. Management science
Operations research
Slater solution
Studies
Tournament solutions
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0377-2217
1872-6860
DOI:10.1016/j.ejor.2009.07.034