New results on the computation of median orders Original Research Article

In this paper, we deal with the following problem: given a weighted tournament T, determine a minimum-weighted set of arcs of T such that reversing these arcs makes T transitive. This problem, which is NP-hard, is a generalization of the Feedback Arc Set problem for digraphs. We improve a branch and bound method with the help of some theoretical results. Among them, a generalization of a covering relation to weighted tournaments is proposed, as well as the computation of three lower bounds of the number of arcs to reverse in T to make it transitive, or still the use of information provided by the “beginning sections” of the linear orders generated in the branch and bound tree. We give some indications upon the computational efficiency of these results.