NP-completeness results concerning greedy and super greedy linear extensions
type: Item
instance of: scholarly article
title: NP-completeness results concerning greedy and super greedy linear extensions
zbMATH Open document ID: 0611.06004
DOI: 10.1007/BF00390103
author: H. A. Kierstead
published in: Order
publication date: 1986-01-01T00:00:00Z
review text: The problem of determining that an ordered set is not greedy is NP- complete. Let \({\mathcal P}=(P,\leq)\) be an ordered set and \({\mathcal P}'\) a partial extension of \({\mathcal P}\). The problem of determining that there exists a (super) greedy linear extension of \({\mathcal P}\) which is also an extension of \({\mathcal P}'\) is NP-complete.
Mathematics Subject Classification ID: 06A06
zbMATH DE Number: 3987338
zbMATH Keywords: ordered set
zbMATH Keywords: greedy
zbMATH Keywords: NP-complete
zbMATH Keywords: partial extension
zbMATH Keywords: linear extension
reviewed by: Nicolae Ţăndăreanu
MaRDI profile type: Publication
cites work: Q4200070
cites work: The complexity of theorem-proving procedures
cites work: On the size of jump-critical ordered sets
cites work: Representing an ordered set as the intersection of super greedy linear extensions
cites work: Optimal Linear Extensions by Interchanging Chains
cites work: Constructing greedy linear extensions by interchanging chains
full work available at URL: https://doi.org/10.1007/bf00390103
OpenAlex ID: W2057481107
description: scientific article; zbMATH DE number 3987338