|
|||||
|
|
Computing the dimension ofN-free ordered sets is NP-complete |
|
| Authors: | H. A. Kierstead S. G. Penrice |
| Affiliation: | (1) Department of Mathematics, Arizona State University, 85287 Tempe, AZ, USA |
| Abstract: | We show that the problem of deciding whether anN-free ordered set has dimension at most 3 is NP-complete.Both authors supported by Office of Naval Research contract N00014-85K-0494. |
| Keywords: | Ordered set dimension N-free NP-complete |
| 本文献已被 SpringerLink 等数据库收录！ | |