Search

In this paper, we try to enumerate the results dealing with the combinatorial and algorithmic aspects of the median orders and Slater orders of tournaments. Most of the quoted results may be found in the different papers devoted to these topics ; some others are new ones. Dans cet article, nous essayons de faire le point sur les résultats concernant les aspects combinatoires et algorithmiques des ordres médians et des ordres de Slater des tournois. La plupart des résultats recensés sont tirés de différentes publications ; plusieurs sont originaux.

We present a generalization of minimal separation in an undirected graph, and show how the maximal rectangles of the adjacency matrix describe such separators, and form an ortholattice, which we call the Separability Lattice. Furthermore, for any given ortholattice L, we show that there does not exist a unique minimal graph of which L is the Separability Lattice. We establish a necessary and sufficient condition for the existence of such a graph. The end of the paper deals with algorithmic considerations on the class of orthocom-plemented lattices. Nous présentons une généralisation de la notion de séparateur minimal dans un graphe non orienté, et nous montrons que ces séparateurs sont représentés par les rectangles maximaux de la matrice d'adjacence, structurés en un orthotreillis, que nous appelons treillis de séparabilité. Réciproquement, tant donné un orthotreillis, nous montrons qu'il n'existe pas en général un unique graphe minimal dont il serait treillis de séparabilité. Nous donnons une condition nécessaire et suffisante pour que cette dernière propriété soit vérifiée. Le dernier paragraphe de l'article contient des considérations algorithmiques relatives aux treillis orthocomplémentés.

Multiway dissimilarities naturally generalize the usual two-way dissimilarities. In this paper, particular classes of multiway dissimilarities are studied as well as some models for deriving from a dissimilarity of a given number of ways, one of a greater or a lower number of ways. An application to clustering systems specification has led to a one-to-one correspondence between a class of multiway dissimilarities and a family of stratified clustering systems. Les dissimilarités multivoies sont une généralisation naturelle des dissimilarités usuelles deux voies. Dans ce papier, des classes de dissimilarités multivoies sont étudiées, ainsi que des modèles de passage d'un nombre de voies donné à un autre nombre de voies. Une application à la spécification de systèmes classifiants a conduit à une bijection entre une classe de dissimilarités multivoies et une famille de systèmes stratifiés de classification.

Doignon and Fiorini (2003)determine all facets of the approval-voting polytope, thus offering a characterization of the size-independent model for approval voting of Falmagne and Regenwetter (1996). The present paper is a follow-up. It first provides an alternate proof of the basic result, which is more direct and at the same time constructive. Then, the combinatorial interpretation of the facets of the approval-voting polytope is further investigated. Finally, we derive a linear description of the polytope in case the number of alternatives equals 6. Doignon et Fiorini (2003) déterminent toutes les facettes du polytope du vote approbatoire. Ils livrent ainsi une caractérisation d'un modèle probabiliste dû à Falmagne et Regenwetter (1996) : le modèle sous indépendance de taille pour le vote approbatoire. Le présent texte est un complément. Il donne d'abord une preuve alternative du résultat central, plus directe mais aussi constructive. L'interprétation combinatoire des facettes du polytope du vote approbatoire est ensuite étudiée. Enfin, une description linéaire du polytope est obtenue dans le cas où le nombre d'alternatives vaut 6.