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 条

[21] Complexity of clique coloring and related problems [J].

Marx, Daniel .

THEORETICAL COMPUTER SCIENCE, 2011, 412 (29) :3487-3500

[22] Complexity of Conservative Constraint Satisfaction Problems [J].

Bulatov, Andrei A. .

ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 2011, 12 (04)

[23] The issue of complexity in the research problems of industry [J].

Mrozinska, Agnieszka .

PRACE KOMISJI GEOGRAFII PRZEMYSLU POLSKIEGO TOWARZYSTWA GEOGRAFICZNEGO-STUDIES OF THE INDUSTRIAL GEOGRAPHY COMMISSION OF THE POLISH GEOGRAPHICAL SOCIETY, 2015, 29 (04) :26-39

[24] Complexity of Cycle Transverse Matching Problems [J].

Churchley, Ross ;

Huang, Jing ;

Zhu, Xuding .

COMBINATORIAL ALGORITHMS, 2011, 7056 :135-+

[25] The Complexity of Temporal Constraint Satisfaction Problems [J].

Bodirsky, Manuel ;

Kara, Jan .

JOURNAL OF THE ACM, 2010, 57 (02)

[26] The complexity results of the sparse optimization problems and reverse convex optimization problems [J].

Zhongyi Jiang ;

Qiying Hu .

Optimization Letters, 2020, 14 :2149-2160

[27] The complexity results of the sparse optimization problems and reverse convex optimization problems [J].

Jiang, Zhongyi ;

Hu, Qiying .

OPTIMIZATION LETTERS, 2020, 14 (08) :2149-2160

[28] THE COMPLEXITY OF SYMMETRIC BOOLEAN PARITY HOLANT PROBLEMS [J].

Guo, Heng ;

Lu, Pinyan ;

Valiant, Leslie G. .

SIAM JOURNAL ON COMPUTING, 2013, 42 (01) :324-356

[29] More results on the complexity of identifying problems in graphs [J].

Hudry, Olivier ;

Lobstein, Antoine .

THEORETICAL COMPUTER SCIENCE, 2016, 626 :1-12

[30] Complexity Results for Some Global Optimization Problems [J].

Locatelli, M. .

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2009, 140 (01) :93-102

← 1 2 3 4 5 →