Abstract
We show that the problems of deciding whether an ordered set has at least k depth-first linear extensions and whether an ordered set has at least k greedy linear extensions are NP-hard.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 295-303 |
| Number of pages | 9 |
| Journal | Order |
| Volume | 6 |
| Issue number | 3 |
| DOIs | |
| State | Published - Sep 1989 |
Keywords
- AMS subject classifications (1980): 06A10, 68C25
- Depth-first linear extension
- NP-complete
- greedy linear extension
- ordered set
ASJC Scopus subject areas
- Algebra and Number Theory
- Geometry and Topology
- Computational Theory and Mathematics