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 条

[41] THE COMPLEXITY OF COMBINATIONS OF QUALITATIVE CONSTRAINT SATISFACTION PROBLEMS [J].

Bodirsky, Manuel ;

Greiner, Johannes .

LOGICAL METHODS IN COMPUTER SCIENCE, 2020, 16 (01)

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

M. Locatelli .

Journal of Optimization Theory and Applications, 2009, 140 :93-102

[43] Complexity of some problems in positive and related calculi [J].

Maksimova, L .

THEORETICAL COMPUTER SCIENCE, 2003, 303 (01) :171-185

[44] Parameterized Complexity of Streaming Diameter and Connectivity Problems [J].

Oostveen, Jelle J. ;

van Leeuwen, Erik Jan .

ALGORITHMICA, 2024, 86 (09) :2885-2928

[45] The complexity of wicked problems in large scale change [J].

Waddock, Sandra ;

Meszoely, Greta M. ;

Waddell, Steve ;

Dentoni, Domenico .

JOURNAL OF ORGANIZATIONAL CHANGE MANAGEMENT, 2015, 28 (06) :993-1012

[46] Specialty Boundaries, Compound Problems, and Collaborative Complexity [J].

Gerson E.M. .

Biological Theory, 2009, 4 (3) :247-252

[47] Complexity classification of some edge modification problems [J].

Natanzon, A ;

Shamir, R ;

Sharan, R .

DISCRETE APPLIED MATHEMATICS, 2001, 113 (01) :109-128

[48] Algorithms and Complexity Results for Genome Mapping Problems [J].

Rajaraman, Ashok ;

Pereira Zanetti, Joao Paulo ;

Manuch, Jan ;

Chauve, Cedric .

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, 2017, 14 (02) :418-430

[49] Two-stage stochastic minimum s - t cut problems: Formulations, complexity and decomposition algorithms [J].

Steffen, Rebennack ;

Prokopyev, Oleg A. ;

Singh, Bismark .

NETWORKS, 2020, 75 (03) :235-258

[50] A survey on the complexity of tournament solutions [J].

Hudry, Olivier .

MATHEMATICAL SOCIAL SCIENCES, 2009, 57 (03) :292-303

← 1 2 3 4 5 →