research article
A note on order preserving matchings
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.
Type
research article
Web of Science ID
WOS:A1989AN32000004
Author(s)
Date Issued
1989
Published in
Volume
8
Issue
4
Start page
197
End page
200
Note
PRO 89.01
Editorial or Peer reviewed
REVIEWED
Written at
EPFL
EPFL units
Available on Infoscience
February 13, 2006
Use this identifier to reference this record