A note on order preserving matchings
Margot, F.; Prodon, A.; Liebling, Th. M.
1989

Résumé

We study order preserving injections or bipartite matchings from poset V1 to poset V2. When V1 is totally ordered, we give an efficient algorithm for the associated optimization problem and the convex hull of the corresponding characteristic vectors. If V2 is totally ordered and V1 is not, the problem is NP-complete.

Détails

Titre A note on order preserving matchings
Auteur(s) Margot, F. ; Prodon, A. ; Liebling, Th. M.
Publié dans Operations Research Letters
Volume 8
Numéro 4
Pages 197-200
Date 1989
Note PRO 89.01
DOI https://doi.org/10.1016/0167-6377(89)90060-6
Autres identifiant(s) Afficher la publication dans Web of Science
Laboratoires ROSO
Le document apparaît dans Production scientifique et compétences > SB - Faculté des sciences de base > SB Archives > ROSO - Chaire de recherche opérationnelle SO
Production scientifique et compétences > SB - Faculté des sciences de base > Mathématiques
Publications validées par des pairs
Travail produit à l'EPFL
Articles de journaux
Publié
Date de création de la notice 2006-02-13