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

Charon-Fournier, Irène, Germa, Anne, and Hudry, Olivier. "Utilisation des scores dans des méthodes exactes déterminant les ordres médians de tournois." Mathématiques et Sciences Humaines 119 (1992): 53-74. <http://eudml.org/doc/94429>.

@article{Charon1992,
abstract = {Dans cet article, nous utilisons un paramètre $\sigma (T)$ 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(T)$ 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(T)$ et un ordre médian de $T$ pour les tournois $T$ tels que $\sigma (T)$ soit égal à $1$ ou $2$. Puis nous donnons des résultats expérimentaux sur l’utilisation de $\sigma (T)$ dans une méthode arborescente par séparation et évaluation progressive («Branch and Bound») déterminant, pour tout tournoi $T, i(T)$ et les ordres médians de $T$.},
author = {Charon-Fournier, Irène, Germa, Anne, Hudry, Olivier},
journal = {Mathématiques et Sciences Humaines},
keywords = {scores; tournament; median orders; algorithms; branch and bound method},
language = {fre},
pages = {53-74},
publisher = {Ecole des hautes-études en sciences sociales},
title = {Utilisation des scores dans des méthodes exactes déterminant les ordres médians de tournois},
url = {http://eudml.org/doc/94429},
volume = {119},
year = {1992},
}

TY - JOUR
AU - Charon-Fournier, Irène
AU - Germa, Anne
AU - Hudry, Olivier
TI - Utilisation des scores dans des méthodes exactes déterminant les ordres médians de tournois
JO - Mathématiques et Sciences Humaines
PY - 1992
PB - Ecole des hautes-études en sciences sociales
VL - 119
SP - 53
EP - 74
AB - Dans cet article, nous utilisons un paramètre $\sigma (T)$ 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(T)$ 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(T)$ et un ordre médian de $T$ pour les tournois $T$ tels que $\sigma (T)$ soit égal à $1$ ou $2$. Puis nous donnons des résultats expérimentaux sur l’utilisation de $\sigma (T)$ dans une méthode arborescente par séparation et évaluation progressive («Branch and Bound») déterminant, pour tout tournoi $T, i(T)$ et les ordres médians de $T$.
LA - fre
KW - scores; tournament; median orders; algorithms; branch and bound method
UR - http://eudml.org/doc/94429
ER -