Pages that link to "Item:Q581427"
From MaRDI portal
The following pages link to NP-completeness properties about linear extensions (Q581427):
Displaying 18 items.
- An improved approximation ratio for the jump number problem on interval orders (Q391978) (← links)
- The shrinking property for NP and coNP (Q627189) (← links)
- Minimizing the sum cost in linear extensions of a poset (Q630194) (← links)
- NP-completeness results concerning greedy and super greedy linear extensions (Q1087567) (← links)
- On minimizing jumps for ordered sets (Q1177708) (← links)
- Tackling the jump number of interval orders (Q1182058) (← links)
- A greedy reduction algorithm for setup optimization (Q1183348) (← links)
- On a setup optimization problem for interval orders (Q1195865) (← links)
- Computing the jump number on semi-orders is polynomial (Q1329825) (← links)
- The setup polyhedron of series-parallel posets (Q1372744) (← links)
- A weighted version of the jump number problem on two-dimensional orders is NP-complete (Q1404375) (← links)
- An improved algorithm for the jump number problem (Q1603444) (← links)
- The jump number problem on interval orders: A 3/2 approximation algorithm (Q1898347) (← links)
- The arboreal jump number of an order (Q1943701) (← links)
- A refined analysis on the jump number problem of interval orders (Q2353641) (← links)
- On the power of graph searching for cocomparability graphs (Q2801333) (← links)
- The Shrinking Property for NP and coNP (Q3507436) (← links)
- On Hardness of Multilinearization and VNP-Completeness in Characteristic 2 (Q4973864) (← links)