On the complexity of Slater's problems

被引：12
作者：
Hudry, Olivier [1 ]
机构：
[1] Ecole Natl Super Telecommun Bretagne, F-75634 Paris 13, France
来源：
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2010年 / 203卷 / 01期
关键词：
Complexity; Tournament solutions; Slater solution; Majority tournament; BANKS WINNERS; TOURNAMENTS; RECOGNIZE; DIFFICULT;
D O I：
10.1016/j.ejor.2009.07.034
中图分类号：
C93 [管理学];
学科分类号：
12 ; 1201 ; 1202 ; 120202 ;
摘要：
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. (C) 2009 Elsevier B.V. All rights reserved.
引用
收藏
页码：216 / 221
页数：6
相关论文
共 50 条
12345