✦ LIBER ✦

A survey on the complexity of tournament solutions

✍ Scribed by Olivier Hudry

Publisher: Elsevier Science
Year: 2009
Tongue: English
Weight: 560 KB
Volume: 57
Category: Article
ISSN: 0165-4896
DOI: 10.1016/j.mathsocsci.2008.12.002

No coin nor oath required. For personal study only.

✦ Synopsis

In voting theory, the result of a paired comparison method such as the one suggested by Condorcet can be represented by a tournament, i.e., a complete asymmetric directed graph. When there is no Condorcet winner, i.e., a candidate preferred to any other candidate by a majority of voters, it is not always easy to decide who is the winner of the election. Different methods, called tournament solutions, have been proposed for defining the winners. They differ in their properties and usually lead to different winners. Among these properties, we consider in this survey the algorithmic complexity of the most usual tournament solutions: some are polynomial, some are NP-hard, while the complexity status of others remains unknown.

📜 SIMILAR VOLUMES

Generalizations of tournaments: A survey

✍ Bang-Jensen, J�rgen; Gutin, Gregory 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 376 KB

We survey results concerning various generalizations of tournaments. The reader will see that tournaments are by no means the only class of directed graphs with a very rich structure. We describe, among numerous other topics mostly related to paths and cycles, results on hamiltonian paths and cycle

On the evolution of a random tournament

✍ Tomasz Łuczak; Andrzej Ruciński; Jacek Gruszka 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 280 KB

A survey of techniques in applied comput

A survey of techniques in applied computational complexity

✍ Robert Meersman 📂 Article 📅 1975 🏛 Elsevier Science 🌐 English ⚖ 751 KB

On the existence of specified cycles in

On the existence of specified cycles in a tournament

✍ Abdelhamid Benhocine; A. Pawel Wojda 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 241 KB 👁 1 views

For 2 s p s n and n 2 3, D(n, p) denotes the digraph with n vertices obtained from a directed cycle of length n by changing the orientation of p -1 consecutives edges. In this paper, we prove that every tournament of order n 2 7 contains D(n, p ) for p = 2, 3, ..., n. Furthermore, we determine the t

The complexity of finding generalized pa

The complexity of finding generalized paths in tournaments

✍ Pavol Hell; Moshe Rosenfeld 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 405 KB

Complexity of cyclic scheduling problems

Complexity of cyclic scheduling problems: A state-of-the-art survey

✍ Eugene Levner; Vladimir Kats; David Alcaide López de Pablo; T.C.E. Cheng 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 325 KB

## a b s t r a c t In this survey we review the current complexity status of basic cyclic scheduling models. We start with the formulations of three fundamental cyclic scheduling problems, namely the cyclic jobshop, cyclic flowshop, and cyclic project scheduling problems. We present state-of-the-ar