NP-completeness properties about linear extensions

DOI10.1007/BF00337693zbMath0627.06005MaRDI QIDQ581427

Vincent Bouchitte, Michel A. Habib

Publication date: 1987

Published in: Order (Search for Journal in Brave)

zbMATH Keywords

NP-completenessNP-harddepth-first greedy linear extensionsDilworth partially ordered setsDilworth posetsjump number problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Partial orders, general (06A06)

Related Items (13)

Computing the jump number on semi-orders is polynomial ⋮ The jump number problem on interval orders: A 3/2 approximation algorithm ⋮ The setup polyhedron of series-parallel posets ⋮ An improved approximation ratio for the jump number problem on interval orders ⋮ The arboreal jump number of an order ⋮ Minimizing the sum cost in linear extensions of a poset ⋮ On minimizing jumps for ordered sets ⋮ Tackling the jump number of interval orders ⋮ A greedy reduction algorithm for setup optimization ⋮ On a setup optimization problem for interval orders ⋮ On the Power of Graph Searching for Cocomparability Graphs ⋮ An improved algorithm for the jump number problem ⋮ A refined analysis on the jump number problem of interval orders

Cites Work

• Unnamed Item
• Unnamed Item
• NP-completeness results concerning greedy and super greedy linear extensions
• A decomposition theorem for partially ordered sets
• The Complexity of the Partial Order Dimension Problem
• Optimal Linear Extensions by Interchanging Chains
• Algorithmic Approaches to Setup Minimization
• Minimizing Setups for Cycle-Free Ordered Sets
• The complexity of theorem-proving procedures

This page was built for publication: NP-completeness properties about linear extensions