A note on order preserving matchings (Q1121175)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A note on order preserving matchings |
scientific article |
Statements
A note on order preserving matchings (English)
0 references
1989
0 references
Order preserving injections from a poset U to a poset V are studied. If U is totally ordered, a dynamic programming algorithm is given to solve this case. For the same case a polyhedral characterization is proved. If V is totally ordered and U is not, the problem is NP-complete.
0 references
matchings
0 references
Order preserving injections
0 references
polyhedral characterization
0 references
totally ordered
0 references
NP-complete
0 references
