Utilisation des scores dans des méthodes exactes déterminant les ordres médians de tournois

Charon-Fournier, Irène  ; Germa, Anne  ; Hudry, Olivier 

Mathématiques informatique et sciences humaines, Tome 119 (1992), pp. 53-74

Résumé (VO)

Dans cet article, nous utilisons un paramètre $\sigma \left(T\right)$ défini à partir des scores d’un tournoi $T$ pour déterminer les ordres médians de $T$. Ce paramètre évalue un éloignement entre le tournoi $T$ et les tournois transitifs ayant le même nombre de sommets. Appelant $i\left(T\right)$ le nombre minimum d’arcs à inverser pour rendre $T$ transitif, et $n$ le nombre de sommets de $T$, nous proposons d’abord deux algorithmes linéaires en n calculant $i\left(T\right)$ et un ordre médian de $T$ pour les tournois $T$ tels que $\sigma \left(T\right)$ soit égal à $1$ ou $2$. Puis nous donnons des résultats expérimentaux sur l’utilisation de $\sigma \left(T\right)$ dans une méthode arborescente par séparation et évaluation progressive («Branch and Bound») déterminant, pour tout tournoi $T,i\left(T\right)$ et les ordres médians de $T$.

Abstract

In this paper, we use a parameter $\sigma \left(T\right)$ defined from the scores of a tournament $T$ to determine the median orders of $T$. This parameter measures a remoteness between the tournament $T$ and the transitive tournaments with the same number of vertices. Calling $i\left(T\right)$ the minimum number of arcs that it is necessary to reverse to make $T$ transitive, and $n$ the number of vertices of $T$, we give first two linear (in $n$) algorithms to compute $i\left(T\right)$ and a median order of $T$ for $T$ such that $\sigma \left(T\right)$ is equal to $1$ or $2$. Then we give experimental results on the use of $\sigma \left(T\right)$ in a Branch and Bound method designed to compute $i\left(T\right)$ and the median orders of $T$.