NP-completeness properties about linear extensions
From MaRDI portal
Publication:581427
DOI10.1007/BF00337693zbMath0627.06005MaRDI QIDQ581427
Michel A. Habib, Vincent Bouchitte
Publication date: 1987
Published in: Order (Search for Journal in Brave)
NP-completeness; NP-hard; depth-first greedy linear extensions; Dilworth partially ordered sets; Dilworth posets; jump number problem
Related Items
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, Computing the jump number on semi-orders is polynomial, The setup polyhedron of series-parallel posets, An improved algorithm for the jump number problem, The jump number problem on interval orders: A 3/2 approximation algorithm
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