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 条
  • [1] Theories of complexity and their problems
    Poser, Hans
    FRONTIERS OF PHILOSOPHY IN CHINA, 2007, 2 (03) : 423 - 436
  • [2] The Computational Complexity of Choice Sets
    Brandt, Felix
    Fischer, Felix
    Harrenstein, Paul
    MATHEMATICAL LOGIC QUARTERLY, 2009, 55 (04) : 444 - 459
  • [3] On the complexity of Nurse Rostering problems
    den Hartog, Steven J. M.
    Hoogeveen, Han
    van der Zanden, Tom C.
    OPERATIONS RESEARCH LETTERS, 2023, 51 (05) : 483 - 487
  • [4] On the complexity of the bondage and reinforcement problems
    Hu, Fu-Tao
    Xu, Jun-Ming
    JOURNAL OF COMPLEXITY, 2012, 28 (02) : 192 - 201
  • [5] Qubit complexity of continuous problems
    A. Papageorgiou
    J. F. Traub
    Journal of Fixed Point Theory and Applications, 2009, 6 : 295 - 304
  • [6] ON THE COMPLEXITY OF PACKAGE RECOMMENDATION PROBLEMS
    Deng, Ting
    Fan, Wenfei
    Geerts, Floris
    SIAM JOURNAL ON COMPUTING, 2013, 42 (05) : 1940 - 1986
  • [7] The complexity of problems in wireless communication
    Lingsheng Shi
    Huandong Wang
    Telecommunication Systems, 2017, 65 : 419 - 427
  • [8] Qubit complexity of continuous problems
    Papageorgiou, A.
    Traub, J. F.
    JOURNAL OF FIXED POINT THEORY AND APPLICATIONS, 2009, 6 (02) : 295 - 304
  • [9] On the complexity of equational problems in CNF
    Pichler, R
    JOURNAL OF SYMBOLIC COMPUTATION, 2003, 36 (1-2) : 235 - 269
  • [10] The complexity of problems in wireless communication
    Shi, Lingsheng
    Wang, Huandong
    TELECOMMUNICATION SYSTEMS, 2017, 65 (03) : 419 - 427
12345