The theory of directed graphs has developed enormously over recent decades, yet this book
(first published in 2000) remains the only book to cover more than a small fraction of the …

We address optimization problems in which we are given contradictory pieces of input
information and the goal is to find a globally consistent solution that minimizes the extent of …

A tournament is an oriented complete graph. The feedback arc set problem for tournaments
is the optimization problem of determining the minimum possible number of edges of a given …

The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments Page 1 Combinatorics,
Probability and Computing (2007) 16, 1–4. c 2006 Cambridge University Press …

In this paper we introduce a new class of directed graphs called locally semicomplete
digraphs. These are defined to be those digraphs for which the following holds: for every …

We consider the following simple algorithm for feedback arc set problem in weighted
tournaments—order the vertices by their weighted indegrees. We show that this algorithm …

Voting (or rank aggregation) is a general method for aggregating the preferences of multiple
agents. One important voting rule is the Slater rule. It selects a ranking of the alternatives (or …

We consider the following simple algorithm for feedback arc set problem in weighted
tournaments: order the vertices by their weighted indegrees. We show that this algorithm has …

Let D be a digraph and o EV (D) an arbitrary vertex of D. An out-branching rooted at v is a
spanning tree which is directed in such a way that that each x# v has one edge coming in …

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 …