Un algorithme de partition d'un produit direct d'ordres totaux en un nombre minimum de chaînes
Pichon, Emmanuel ; Lenca, Philippe ; Guillet, Fabrice ; Wang, Jian Wei
Mathématiques et Sciences humaines, Tome 128 (1994), p. 5-15 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

Cette étude s'inscrit dans un prolongement algorithmique d'un travail de Bruno Leclerc, publié dans cette revue, qui discute de la taille maximum d'une antichaîne dans un produit direct P d'ordres totaux. On y présente un algorithme de partitionnement de P en un nombre minimum de chaînes. Enfin, on décrit brièvement une application à l'extraction de connaissance.

This paper concerns an algorithmic extension of a work by Bruno Leclerc published in this Journal. He discusses the maximum cardinality of an antichain in the direct product P of linear orders. We present an algorithm for partitioning P into a minimum number of chains. We also briefly describe an application in the field of knowledge extraction.

Publié le : 1994-01-01
@article{MSH_1994__125__5_0,
     author = {Pichon, Emmanuel and Lenca, Philippe and Guillet, Fabrice and Wang, Jian Wei},
     title = {Un algorithme de partition d'un produit direct d'ordres totaux en un nombre minimum de cha\^\i nes},
     journal = {Math\'ematiques et Sciences humaines},
     volume = {128},
     year = {1994},
     pages = {5-15},
     mrnumber = {1281944},
     zbl = {0802.06001},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/MSH_1994__125__5_0}
}

Pichon, Emmanuel; Lenca, Philippe; Guillet, Fabrice; Wang, Jian Wei. Un algorithme de partition d'un produit direct d'ordres totaux en un nombre minimum de chaînes. Mathématiques et Sciences humaines, Tome 128 (1994) pp. 5-15. http://gdmltest.u-ga.fr/item/MSH_1994__125__5_0/

[1] Anderson I., Combinatorics of Finite sets, Oxford, Clarendon press,1987. | MR 892525 | Zbl 0604.05001

[2] Barthelemy J.P., Mullet E., "Choice basis: A model for multi-attribute preference", British journal of Mathematical and Statistical Psychology, 39 (1986), p. 106-124. | MR 966946 | Zbl 0606.62129

[3] Barthelemy J.P., Mullet E. (1992), "A model of selection by aspects", Acta Psychologica, 79, 1-19.

[4] Behrendt G., "The lattice of antichain cutsets of a partially ordered set", Discrete math., 89 (1991), p. 201-202. | MR 1107635 | Zbl 0731.06002

[5] D N.G., Tengbergen C., Kruyswijk D., "On the set of divisors of a number", Nieuw Arch. Wiskd., 23 (1951), p. 191-193. | MR 43115 | Zbl 0043.04301

[6] Leclerc B., "Sur le nombre d'éléments des niveaux des produits de chaînes et des treillis permutoèdres", Math. Inf. Sci. Hum., 112 (1990), p. 37-48. | Numdam | MR 1096919 | Zbl 0787.06001

[7] Mullet E., L'intégration des informations dans le jugement et la décision, Thèse de Doctorat d'Etat (1985), Université René Descartes, Sciences Humaines, Sorbonne.

[8] Griggs J.R., "Maximum antichains in the product of chains ", Order, 1 (1984), p. 21-28. | MR 745586 | Zbl 0561.06003

[9] Griggs J.R., "Problems on chain partitions", Discrete Math., 72 (1988), p.157-162. | MR 975534 | Zbl 0665.06003

[10] Sands B., "Counting antichains in finite partially ordered sets", Discrete Math., 35 (1981), p. 213-228. | MR 620674 | Zbl 0463.06002