NP-Completeness results concerning greedy and super greedy linear extensions |
| |
| Authors: | Henry A Kierstead |
| |
| Institution: | (1) Department of Mathematics, University of South Carolina, 29208 Columbia, SC, USA;(2) Department of Mathematics and Statistics, University of Calgary, T2N 1N4 Calgary, Alberta, Canada |
| |
| Abstract: | Various problems concerning greedy and super greedy linear extensions are shown to be NP-complete. In particular, the problem,
due to Cogis, of determining that an ordered set is not greedy is NP-complete, as is the problem, due to Rival and Zaguia,
of determining whether an ordered set has a greedy linear extension, which satisfies certain additional constraints.
The author was supported in part by ONR grant N00014-85K-0494 and NSERC grants 69-3378. 69-0259, and 69-1325. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
