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.
@article{MSH_1996__133__23_0, author = {Charon, Ir\`ene and Hudry, Olivier and Woirgard, Fr\'ed\'eric}, title = {Ordres m\'edians et ordres de {Slater} des tournois}, journal = {Math\'ematiques informatique et sciences humaines}, pages = {23--56}, publisher = {Ecole des hautes-\'etudes en sciences sociales}, volume = {133}, year = {1996}, mrnumber = {1411798}, zbl = {0870.90095}, language = {fr}, url = {http://www.numdam.org/item/MSH_1996__133__23_0/} }
TY - JOUR AU - Charon, Irène AU - Hudry, Olivier AU - Woirgard, Frédéric TI - Ordres médians et ordres de Slater des tournois JO - Mathématiques informatique et sciences humaines PY - 1996 SP - 23 EP - 56 VL - 133 PB - Ecole des hautes-études en sciences sociales UR - http://www.numdam.org/item/MSH_1996__133__23_0/ LA - fr ID - MSH_1996__133__23_0 ER -
%0 Journal Article %A Charon, Irène %A Hudry, Olivier %A Woirgard, Frédéric %T Ordres médians et ordres de Slater des tournois %J Mathématiques informatique et sciences humaines %D 1996 %P 23-56 %V 133 %I Ecole des hautes-études en sciences sociales %U http://www.numdam.org/item/MSH_1996__133__23_0/ %G fr %F MSH_1996__133__23_0
Charon, Irène; Hudry, Olivier; Woirgard, Frédéric. Ordres médians et ordres de Slater des tournois. Mathématiques informatique et sciences humaines, Volume 133 (1996), pp. 23-56. http://www.numdam.org/item/MSH_1996__133__23_0/
[1] Problem" in Theory of graphs and its applications, Proc. Coll. Smolenice, Czech. Acad. Sci. Publ.
(1964) "[2] The maximum number of Hamiltonian paths in tournaments ", Combinatorica, 10, 319-324. | MR | Zbl
(1990) "[3] The probabilistic method, J. Wiley, New York, 1992. | MR | Zbl
et ,[4] Cycles of each length in regular tournaments", Canad. Math. Bull., 10, 283-286. | MR | Zbl
(1967) "[5] Un nouvel algorithme de recherche d'un ordre induit par des comparaisons par paires", in Data analysis and informatics III, E. Diday et al. (sd), North Holland, Amsterdam, 323-343. | MR | Zbl
(1984) "[6] Sophisticated voting outcomes and agenda control ", Social Choice and Welfare, 2, 295-306. | Zbl
(1985) "[7] Covering relations, closest orderings and hamiltonian bypaths in tournaments", Social Choice and Welfare, 8, 355-363. | MR | Zbl
, et (1991) "[8] Complexité algorithmique et problèmes de communication, Masson, Paris. | MR | Zbl
, et (1992),[9] Median linear orders: heuristics and a branch and bound algorithm", EJOR, 41, 313-325. | MR | Zbl
, et (1989) "[10] The reversing number of a digraph", Discrete Applied Mathematics, 60, 39-76. | MR | Zbl
, , , et (1995) "[11] The median procedure in cluster analysis and social choice theory", Mathematical Social Sciences, 1, 235-267. | MR | Zbl
et (1981) "[12] The median procedure in data analysis : new results and open problems", in Classification and related methods of data analysis, H.H. Bock (sd), North Holland, Amsterdam. | MR
et (1988) "[13] Graphes, Gauthier-Villars.
(1970)[14] Hypergraphes, Gauthier-Villars. | Zbl
(1987)[15] Ordres à distance minimum d'un tournoi et graphes partiels sans circuits maximaux", Math. Sci. hum, 37, 5-25. | Numdam | MR | Zbl
(1972) "[16] Une heuristique pour le calcul de l'indice de transitivité d'un tournoi", RAIRO, 10 (3), 83-92. | Numdam | MR
et (1976) "[17] The theory of committees and elections, Cambridge University Press, Londres. | Zbl
(1958)[18] Encadrement de l'indice de Slater d'un tournoi à l'aide de ses scores", Math. Inf. Sci. hum, 118,53-68. | Numdam | Zbl
, et (1992) "[19] Utilisation des scores dans des méthodes exactes déterminant les ordres médians de tournois", Math. Inf. Sci. hum, 119, 53-74. | Numdam | MR | Zbl
, et (1992) "[20] "Random generation of tournaments and asymmetric digraphs with given out-degrees", à paraître dans EJOR. | Zbl
, et ,[21] "A branch and bound method applied to ordinal data analysis", Actes de l' "International Conference on Ordinal and Symbolic Data Analysis" (OSDA), Springer Verlag, à paraître.
, , et ,[22] "New results on the computation of median orders", Actes du "5e Colloque International de Théorie des Graphes et Combinatoire ", soumis pour publication.
, , et ,[23] "Lamarckian genetic algorithms applied to the search of median orders", soumis pour publication.
et ,[24] A 16-vertex tournament for which Banks set and Slater set are disjoint ", soumis pour publication. | Zbl
, et , "[25] Graphs with forbidden subgraphs", Journal of Combinatorial Theory, 10, 1, série B, 12-41. | MR | Zbl
, et (1971) "[26] Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix, Paris.
Caritat (marquis de) (1785)[27] Heuristics for ranking players in a round robin tournament", Computers and Operations Research, 15 (2),135-144. | MR
, et (1988) "[28] Caractérisation des matrices de préférences nettes et méthodes d'agrégation associées", Mathématiques et Sciences Humaines 97, 5-17. | Numdam | MR | Zbl
(1987) "[30] On the maximal cardinality of a consistent set of arcs in a random tournament", Journal of Combinatorial Theory, 35, série B, 328-332. | MR | Zbl
(1983) "[31] On sets of consistent arcs in a tournament", Canad. Math. Bull., 8, 269-271. | MR | Zbl
et (1965) "[32] Condorcet social choice functions", SIAM Journal of Applied Mathematics, 33, 469-489. | MR | Zbl
(1977) "[33] Decomposing weighted digraphs into sums of chains", Discrete Applied Mathematics, 16, 15-31. | MR | Zbl
(1987) "[34] Computers and intractability, a guide to the theory of NP-completeness, Freeman, New York. | MR | Zbl
, et (1979)[35] Tournament rankings ", Management Science, 29 (12), 1385-1392. | MR | Zbl
(1983) "[36] A cutting plane algorithm for the linear ordering problem", Operations Research, 32, 1195-1220. | MR | Zbl
, , (1984) "[37] Optimal triangulation of large real-world input-output-matrices", Statistische Hefte, 25, 261-295.
, , (1984) "[38] Facets of the linear ordering polytope", Mathematical Programming, 33, 43-60. | MR | Zbl
, , (1985) "[39] Order at minimum distance of a valued tournament ", communication à Modélisation, Analyse et Agrégation des Préférences et des Choix (TRAP 3), Marseille-Luminy.
(1988) "[40] How to choose according to partial evaluations ", in Advances in Intelligent Computing, B. Bouchon-Meunier et al. (sd), IPMU'94, Lecture Notes in Computer Sciences n° 945, Springer-Verlag, Berlin-Heidelberg, 611-618.
(1995) "[41] Vainqueurs de Kemeny et tournois difficiles", Math. Inf. Sci. hum, 133; | Numdam | MR | Zbl
(1996) "[42] Selecting varieties using a séries of trials and a combinatorial ordering method", Agronomie, 14, 363-375.
, et (1994) "[43] Les théories de l'intérêt général et le problème logique de l'agrégation", Économie Appliquée, 5 (4), repris dans Eléments de la théorie des jeux, Dunod, Paris, 1968.
(1952) "[44] A coarseness conjecture of Erdös", Journal of Combinatorial Theory, 3, 38-42. | MR | Zbl
(1967) "[45] Seriation using asymmetric proximity measures", Br. J. Math. Statist. Psychol., 29, 32-52. | MR | Zbl
(1976) "[46] Recherche d'ordres médians : complexité, algorithmique et problèmes combinatoires, thèse de doctorat de l'ENST, Paris.
(1989)[47] Sur le nombre d'ordres médians de certains tournois ", Actes des journées Mathématiques Discrètes et Sciences Sociales, Amiens, 56-61.
(1992) "[48] Combinatorics and voting theory : on the number of median orders of tournaments", communication à Conference on combinatorics in the behavioral sciences, Irvine, États-Unis.
et (1994) "[49] Lower and upper bounds of the maximum number of Slater's orders of tournaments", communication au 8e Colloque Franco-Japonais/4e Colloque Franco-Chinois Combinatoire et Informatique, Brest.
et (1995) "[50] Tournaments as feedback arc sets", The Electronic Journal of Combinatorics, 2. | MR | Zbl
(1995) "[51] L'agrégation des opinions individuelles", Informatique et Sciences Humaines, 4, 1-21.
(1969) "[52] On subgraphs without cycles in a tournament", Combinatorial theory and its applications II, Balatonfüred, P. Erdös, A. Renyi et V.T. Sös (sd), Amsterdam, North-Holland, 675-677. | MR | Zbl
(1970) "[53] Polyhedral combinatorics and the acyclic subdigraph problem, Heldermann Verlag, Berlin. | MR | Zbl
(1985)[54] Some equivalence classes in paired comparisons ", Ann. math. Statist., 37, 488-494. | MR | Zbl
(1966) "[55] A new algorithm for ranking players of a round-robin tournament", Computers and Operations Research, 22 (2), 221-226. | Zbl
, , et (1995) "[56] Mathematics without numbers ", Daedalus, 88, 577-591.
(1959) "[58] Slater's winners of a tournament may not be in the Banks set", Social Choice and Welfare, 8, 355-363. | MR | Zbl
et (1991) "[59] Choosing from a tournament : a progress report and some new results", document de travail du CNAM.
, et (1991) "[60] On dominance relations and the structure of animal societies III. The condition for a score structure ", Bulletin of Mathematical Biophysics, 13, 1-19. | MR
(1953) "[61] Solutions de tournois : un spicilège", Math. Inf. Sci. hum, 133. | Numdam | MR | Zbl
(1996) "[62] Sequencing by enumerative methods, Mathematical Centre Tracts n° 69, Mathematisch Centrum, Amsterdam. | MR | Zbl
(1977)[63] Optimisation en analyse ordinale de données, Masson, Paris.
et (1979)[64] A new solution set for tournaments and majority voting : Further graph-theoretical approaches to the theory of voting", American Journal of Political Science, 24 (1), 68-96.
(1980) "[65] Tournois et ordres médians pour une opinion", Mathématiques et Sciences Humaines, 43, 55-73. | Numdam | MR | Zbl
(1973) "[66] Sur diverses formes de la "règle de Condorcet" d'agrégation des préférences", Math. Inf. Sci. hum, 111, 61-71. | Numdam | MR | Zbl
(1990) "[67] Topics on tournaments, Holt, Rinehart and Winston. | MR | Zbl
(1968)[68] On an algorithm of Smith and Payne for determining Slater's i and all nearest adjoining orders ", British Journal of Mathematical and Statistical Psychology, 29, 126-127.
(1976) "[69] Tournament ranking with expected profit in polynomial time", SIAM Journal Disc Math, 1 (3), 372-376. | MR | Zbl
, et (1988) "[70] A polynomial time heuristic for certain subgraph optimization problems with guaranteed lower bound", Discrete Mathematics, 58, 99-104. | MR | Zbl
et (1986) "[71] On set of arcs containing no cycles in tournaments", Canad. Math. Bull., 12, 261-264. | MR | Zbl
(1969) "[72] The linear ordering problem : algorithms and applications, Research and Exposition in Mathematics 8, Heldermann Verlag, Berlin. | MR | Zbl
(1985)[73] Maximum likelihood paired comparison rankings", Biometrika, 53,143-149. | MR | Zbl
, R. et (1966) "[74] Inconsistencies in a schedule of paired comparisons", Biometrika, 48, 303-312.
(1961) "[75] An algorithm for determining Slater's i and all nearest adjoining orders", British Journal of Mathematical and Statistical Psychology 27, 49-52.
et (1974) "[76] Optimal ranking of tournaments ", Networks 1, 135-138. | MR | Zbl
(1971) "[77] Nonconstructive methods in discrete mathematics ", in Studies in Combinatorics, G.C. Rota (sd), Mathematical Association of America, Washington DC, 142-178. | MR | Zbl
(1978) "[78] Ten lectures on the probabilistic method, CBMS-NSF Regional Conference Series in Applied Mathematics N° 52, SIAM, Philadelphie, États-Unis. | MR | Zbl
(1987)[79] Kombinatorikai vizsgálatok az iránított teljes gráffal kapesolatban", Mat. Fiz. Lapok., 50, 223-256, traduit en allemand sous le titre " Untersuchungen über gerichtete vollständige Graphen", Publ. Math. Debrecen, 13 (1966), 145-168. | Zbl
(1943) "[80] Counterexamples to Adám's conjecture on arc reversals in directed graphs", Journal of Combinatorial Theory, 42, série B, 128-130. | MR | Zbl
(1987) "[81] Minimum feedback arc sets for a directed graph", IEEE Trans. of the profes. tech. group in circuit theory, 10 (2), 238-245.
(1963) "