NP-Completeness results concerning greedy and super greedy linear extensions

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

Various problems concerning greedy and super greedy linear extensions are shown to be NP-complete. In particular, the problem, due to Cogis, of determining that an ordered set is not greedy is NP-complete, as is the problem, due to Rival and Zaguia, of determining whether an ordered set has a greedy linear extension, which satisfies certain additional constraints.

Original languageEnglish (US)
Pages (from-to)123-134
Number of pages12
JournalOrder
Volume3
Issue number2
DOIs
StatePublished - Jun 1986
Externally publishedYes

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Geometry and Topology
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'NP-Completeness results concerning greedy and super greedy linear extensions'. Together they form a unique fingerprint.

Cite this