NP-completeness results concerning greedy and super greedy linear extensions

DOI10.1007/BF00390103zbMath0611.06004OpenAlexW2057481107MaRDI QIDQ1087567

Henry A. Kierstead

Publication date: 1986

Published in: Order (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00390103

zbMATH Keywords

ordered setNP-completegreedylinear extensionpartial extension

Mathematics Subject Classification ID

Partial orders, general (06A06)

Related Items (5)

On some new types of greedy chains and greedy linear extensions of partially ordered sets ⋮ Representing an ordered set as the intersection of super greedy linear extensions ⋮ On minimizing the jump number for interval orders ⋮ The number of depth-first searches of an ordered set ⋮ NP-completeness properties about linear extensions

Cites Work

• Unnamed Item
• On the size of jump-critical ordered sets
• Constructing greedy linear extensions by interchanging chains
• Representing an ordered set as the intersection of super greedy linear extensions
• Optimal Linear Extensions by Interchanging Chains
• The complexity of theorem-proving procedures

This page was built for publication: NP-completeness results concerning greedy and super greedy linear extensions