NP-completeness properties about linear extensions
type: Item
instance of: scholarly article
title: NP-completeness properties about linear extensions
zbMATH Open document ID: 0627.06005
DOI: 10.1007/BF00337693
author: Vincent Bouchitté
author: M. A. Habib
published in: Order
publication date: 1987-01-01T00:00:00Z
review text: The authors present ``some complexity results about the construction of depth-first greedy linear extensions''. They prove ``that the recognition of Dilworth partially ordered sets of height 2, as defined by Sysło, is NP-complete. This last result yields a new proof of the NP-completeness of the jump number problem, first proved by Pulleyblank''. The following theorems are presented: Theorem 1. Not depth-first greedy is NP-complete. Theorem 2. Weakly depth-first greedy is NP-hard. Theorem 3. Recognition of Dilworth posets is NP-complete. Corollary. The jump number is NP-hard.
reviewed by: Boleslaw Wojdyło
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4019119
zbMATH Keywords: depth-first greedy linear extensions
zbMATH Keywords: Dilworth partially ordered sets
zbMATH Keywords: NP-completeness
zbMATH Keywords: jump number problem
zbMATH Keywords: NP-hard
zbMATH Keywords: Dilworth posets
MaRDI profile type: Publication
cites work: Q4200070
cites work: The complexity of theorem-proving procedures
cites work: A decomposition theorem for partially ordered sets
cites work: Minimizing Setups for Cycle-Free Ordered Sets
cites work: Algorithmic Approaches to Setup Minimization
cites work: Q4198056
cites work: NP-completeness results concerning greedy and super greedy linear extensions
cites work: Optimal Linear Extensions by Interchanging Chains
cites work: The Complexity of the Partial Order Dimension Problem
description: scientific article; zbMATH DE number 4019119