Ordres médians et ordres de Slater des tournois

 Access to full text

 Full (PDF)

1. [1] Adám, A. (1964) "Problem" in Theory of graphs and its applications, Proc. Coll. Smolenice, Czech. Acad. Sci. Publ. 
2. [2] Alon, N. (1990) "The maximum number of Hamiltonian paths in tournaments ", Combinatorica, 10, 319-324. Zbl0724.05036MR1099246
3. [3] Alon, N. et J. Spencer, The probabilistic method, J. Wiley, New York, 1992. Zbl0767.05001MR1140703
4. [4] Alspach, B. (1967) "Cycles of each length in regular tournaments", Canad. Math. Bull., 10, 283-286. Zbl0148.43602MR213261
5. [5] Arditti, D. (1984) "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. Zbl0565.90030MR787645
6. [6] Banks, J. (1985) "Sophisticated voting outcomes and agenda control ", Social Choice and Welfare, 2, 295-306. Zbl0597.90011
7. [7] Banks, J., G. Bordes et M. Le Breton (1991) "Covering relations, closest orderings and hamiltonian bypaths in tournaments", Social Choice and Welfare, 8, 355-363. Zbl0734.90027MR1129431
8. [8] Barthélemy, J.-P., G. Cohen et A. Lobstein (1992), Complexité algorithmique et problèmes de communication, Masson, Paris. Zbl0765.68005MR1188183
9. [9] Barthélemy, J.-P., A. Guénoche et O. Hudry (1989) "Median linear orders: heuristics and a branch and bound algorithm", EJOR, 41, 313-325. Zbl0689.90003MR1020904
10. [10] Barthélemy, J.-P., O. Hudry, G. Isaak, F.S. Roberts et B. Tesman (1995) "The reversing number of a digraph", Discrete Applied Mathematics, 60, 39-76. Zbl0826.05032MR1339075
11. [11] Barthélemy, J.-P. et B. Monjardet (1981) "The median procedure in cluster analysis and social choice theory", Mathematical Social Sciences, 1, 235-267. Zbl0486.62057MR616379
12. [12] Barthélemy, J.-P. et B. Monjardet (1988) "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. MR999565
13. [13] Berge, C. (1970) Graphes, Gauthier-Villars. 
14. [14] Berge, C. (1987) Hypergraphes, Gauthier-Villars. Zbl0623.05001
15. [15] Bermond, J.-C. (1972) "Ordres à distance minimum d'un tournoi et graphes partiels sans circuits maximaux", Math. Sci. hum, 37, 5-25. Zbl0239.05122MR300927
16. [16] Bermond, J.-C. et Y. Kodratoff (1976) "Une heuristique pour le calcul de l'indice de transitivité d'un tournoi", RAIRO, 10 (3), 83-92. MR416971
17. [17] Black, D. (1958) The theory of committees and elections, Cambridge University Press, Londres. Zbl0091.15706
18. [18] Charon-Fournier, I., A. Germa et O. Hudry (1992) "Encadrement de l'indice de Slater d'un tournoi à l'aide de ses scores", Math. Inf. Sci. hum, 118,53-68. Zbl0846.05040
19. [19] Charon-Fournier, I., A. Germa et O. Hudry (1992) "Utilisation des scores dans des méthodes exactes déterminant les ordres médians de tournois", Math. Inf. Sci. hum, 119, 53-74. Zbl0845.05050MR1195698
20. [20] Charon-Fournier, I., A. Germa et O. Hudry, "Random generation of tournaments and asymmetric digraphs with given out-degrees", à paraître dans EJOR. Zbl0974.05502
21. [21] Charon, I., A. Guénoche, O. Hudry et F. Woirgard, "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. Zbl0897.90003
22. [22] Charon, I., A. Guénoche, O. Hudry et F. Woirgard, "New results on the computation of median orders", Actes du "5e Colloque International de Théorie des Graphes et Combinatoire ", soumis pour publication. Zbl0878.68090
23. [23] Charon, I. et O. Hudry, "Lamarckian genetic algorithms applied to the search of median orders", soumis pour publication. Zbl0907.90009
24. [24] Charon, I., O. Hudry et F. Woirgard, "A 16-vertex tournament for which Banks set and Slater set are disjoint ", soumis pour publication. Zbl0895.05027
25. [25] Chartrand, G., D. Geller et S. Hedetniemi (1971) "Graphs with forbidden subgraphs", Journal of Combinatorial Theory, 10, 1, série B, 12-41. Zbl0223.05101MR285427
26. [26] Condorcet, M.J.A.N. Caritat (marquis de) (1785) Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix, Paris. 
27. [27] Cook, W.D., I. Golan et M. Kress (1988) "Heuristics for ranking players in a round robin tournament", Computers and Operations Research, 15 (2),135-144. MR934628
28. [28] Debord, B. (1987) "Caractérisation des matrices de préférences nettes et méthodes d'agrégation associées", Mathématiques et Sciences Humaines97, 5-17. Zbl0619.90005MR890684
29. [30] De La Vega, W.F. (1983) "On the maximal cardinality of a consistent set of arcs in a random tournament", Journal of Combinatorial Theory, 35, série B, 328-332. Zbl0531.05036MR735201
30. [31] Erdös, P. et J.W. Moon (1965) "On sets of consistent arcs in a tournament", Canad. Math. Bull., 8, 269-271. Zbl0137.43301MR182574
31. [32] Fishburn, P. (1977) "Condorcet social choice functions", SIAM Journal of Applied Mathematics, 33, 469-489. Zbl0369.90002MR449470
32. [33] Fishburn, P. (1987) "Decomposing weighted digraphs into sums of chains", Discrete Applied Mathematics, 16, 15-31. Zbl0606.05028MR878023
33. [34] Garey, M.R., et D.S. Johnson (1979) Computers and intractability, a guide to the theory of NP-completeness, Freeman, New York. Zbl0411.68039MR519066
34. [35] Goddard, S.T. (1983) "Tournament rankings ", Management Science, 29 (12), 1385-1392. Zbl0527.90047MR809110
35. [36] Grötschel, M., M. Jünger, G. Reinelt (1984) "A cutting plane algorithm for the linear ordering problem", Operations Research, 32, 1195-1220. Zbl0554.90077MR775257
36. [37] Grötschel, M., M. Jünger, G. Reinelt (1984) "Optimal triangulation of large real-world input-output-matrices", Statistische Hefte, 25, 261-295. 
37. [38] Grötschel, M., M. Jünger, G. Reinelt (1985) "Facets of the linear ordering polytope", Mathematical Programming, 33, 43-60. Zbl0577.05035MR809748
38. [39] Guénoche, A. (1988) "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. 
39. [40] Guénoche, A. (1995) "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. 
40. [41] Guénoche, A. (1996) "Vainqueurs de Kemeny et tournois difficiles", Math. Inf. Sci. hum, 133; Zbl0870.90096MR1411799
41. [42] Guénoche, A., B. Vandeputte-Riboud et J.-B. Denis (1994) " Selecting varieties using a séries of trials and a combinatorial ordering method", Agronomie, 14, 363-375. 
42. [43] Guilbaud, G.T. (1952) "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. 
43. [44] Guy, R.K. (1967) "A coarseness conjecture of Erdös", Journal of Combinatorial Theory, 3, 38-42. Zbl0149.41501MR216983
44. [45] Hubert, L. (1976) "Seriation using asymmetric proximity measures", Br. J. Math. Statist. Psychol., 29, 32-52. Zbl0334.92040MR429180
45. [46] Hudry, O. (1989) Recherche d'ordres médians : complexité, algorithmique et problèmes combinatoires, thèse de doctorat de l'ENST, Paris. 
46. [47] Hudry, O. (1992) "Sur le nombre d'ordres médians de certains tournois ", Actes des journées Mathématiques Discrètes et Sciences Sociales, Amiens, 56-61. 
47. [48] Hudry, O. et F. Woirgard (1994) "Combinatorics and voting theory : on the number of median orders of tournaments", communication à Conference on combinatorics in the behavioral sciences, Irvine, États-Unis. 
48. [49] Hudry, O. et F. Woirgard (1995) "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. 
49. [50] Isaak, G. (1995) "Tournaments as feedback arc sets", The Electronic Journal of Combinatorics, 2. Zbl0829.68100MR1352570
50. [51] Jacquet-Lagrèze, É. (1969) "L'agrégation des opinions individuelles", Informatique et Sciences Humaines, 4, 1-21. 
51. [52] Jung, H.A. (1970) "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. Zbl0207.23002MR297635
52. [53] Jünger, M. (1985) Polyhedral combinatorics and the acyclic subdigraph problem, Heldermann Verlag, Berlin. Zbl0557.68045MR788691
53. [54] Kadane, J.B. (1966) "Some equivalence classes in paired comparisons ", Ann. math. Statist., 37, 488-494. Zbl0171.40101MR187342
54. [55] Kaykobad, M., Q.N.U. Ahmed, A.T.M. Shafiqul Khalid et R.-A. Bakhtiar (1995) "A new algorithm for ranking players of a round-robin tournament", Computers and Operations Research, 22 (2), 221-226. Zbl0814.90147
55. [56] Kemeny, J.G. (1959) "Mathematics without numbers ", Daedalus, 88, 577-591. 
56. [58] Laffond, G. et J.-F. Laslier (1991) "Slater's winners of a tournament may not be in the Banks set", Social Choice and Welfare, 8, 355-363. Zbl0733.90008MR1129432
57. [59] Laffond, G., J.-F. Laslier et M. Le Breton (1991) "Choosing from a tournament : a progress report and some new results", document de travail du CNAM. 
58. [60] Landau, H.G. (1953) "On dominance relations and the structure of animal societies III. The condition for a score structure ", Bulletin of Mathematical Biophysics, 13, 1-19. MR41412
59. [61] Laslier, J.-F. (1996) "Solutions de tournois : un spicilège", Math. Inf. Sci. hum, 133. Zbl0870.90014MR1411797
60. [62] Lenstra, J.K. (1977) Sequencing by enumerative methods, Mathematical Centre Tracts n° 69, Mathematisch Centrum, Amsterdam. Zbl0407.90025MR443968
61. [63] Marcotorchino, J.-F. et P. Michaud (1979) Optimisation en analyse ordinale de données, Masson, Paris. 
62. [64] Miller, N. (1980) "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. 
63. [65] Monjardet, B. (1973) "Tournois et ordres médians pour une opinion", Mathématiques et Sciences Humaines, 43, 55-73. Zbl0271.05114MR376451
64. [66] Monjardet, B. (1990) "Sur diverses formes de la "règle de Condorcet" d'agrégation des préférences", Math. Inf. Sci. hum, 111, 61-71. Zbl0723.01012MR1082274
65. [67] Moon, J.W. (1968) Topics on tournaments, Holt, Rinehart and Winston. Zbl0191.22701MR256919
66. [68] Phillips, J.P.N. (1976) "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. 
67. [69] Poljak, S., V. Rödl et J. Spencer (1988) "Tournament ranking with expected profit in polynomial time", SIAM Journal Disc Math, 1 (3), 372-376. Zbl0667.05030MR955653
68. [70] Poljak, S. et D. Turzik (1986) "A polynomial time heuristic for certain subgraph optimization problems with guaranteed lower bound", Discrete Mathematics, 58, 99-104. Zbl0585.05032MR820844
69. [71] Reid, K.B. (1969) "On set of arcs containing no cycles in tournaments", Canad. Math. Bull., 12, 261-264. Zbl0181.51901MR250926
70. [72] Reinelt, G. (1985) The linear ordering problem : algorithms and applications, Research and Exposition in Mathematics 8, Heldermann Verlag, Berlin. Zbl0565.68058MR831936
71. [73] Remage Jr., R. et W.A. ThompsonJr. (1966) "Maximum likelihood paired comparison rankings", Biometrika, 53,143-149. Zbl0138.13207MR196854
72. [74] Slater, P. (1961) "Inconsistencies in a schedule of paired comparisons", Biometrika, 48, 303-312. 
73. [75] Smith, A.F.M. et C.D. Payne (1974) "An algorithm for determining Slater's i and all nearest adjoining orders", British Journal of Mathematical and Statistical Psychology27, 49-52. 
74. [76] Spencer, J. (1971) "Optimal ranking of tournaments ", Networks1, 135-138. Zbl0236.05110MR299532
75. [77] Spencer, J. (1978) "Nonconstructive methods in discrete mathematics ", in Studies in Combinatorics, G.C. Rota (sd), Mathematical Association of America, Washington DC, 142-178. Zbl0407.05001MR513005
76. [78] Spencer, J. (1987) Ten lectures on the probabilistic method, CBMS-NSF Regional Conference Series in Applied Mathematics N° 52, SIAM, Philadelphie, États-Unis. Zbl0703.05046MR929258
77. [79] Szele, T. (1943) "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. Zbl0178.57703
78. [80] Thomassen, C. (1987) "Counterexamples to Adám's conjecture on arc reversals in directed graphs", Journal of Combinatorial Theory, 42, série B, 128-130. Zbl0609.05041MR872413
79. [81] Younger, D.H. (1963) "Minimum feedback arc sets for a directed graph", IEEE Trans. of the profes. tech. group in circuit theory, 10 (2), 238-245. 

1. Olivier Hudry, Nombre maximum d’ordres de Slater des tournois $T$ vérifiant $\sigma \left(T\right)=1$
2. Jean-François Laslier, Solutions de tournois : un spicilège
3. Alain Guénoche, Vainqueurs de Kemeny et tournois difficiles