NP-completeness properties about linear extensions |
| |
| Authors: | Vincent Bouchitte Michel Habib |
| |
| Affiliation: | (1) Département Informatique Appliquée, Ecole des Mines de Saint-Etienne, 158 cours Fauriel, 42023 Saint-Etienne cedex 2, France;(2) LIB (Laboratoire commun ENST Br et UBO), Département Informatique et Réseaux, Ecole Nationale Supérieure des Télécommunications de Bretagne, ZI de Kernevent, BP 832, 29285, Brest cedex, France |
| |
| 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. |
| |
| Keywords: | 06A10 68C25 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
