ISSN:
1572-9273
Keywords:
06A10
;
68C25
;
Jump number
;
greedy linear extensions
;
Dilworth posets
;
satisfiability
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract Following the pioneering work of Kierstead, we present here some complexity results about the construction of depth-first greedy linear extensions. We prove that the recognition of Dilworth partially ordered sets of height 2, as defined by Syslo, is NP-complete. This last result yields a new proof of the NP-completeness of the jump number problem, first proved by Pulleyblank.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00337693
Permalink