NP-completeness properties about linear extensions

DOI10.1007/BF00337693MaRDI QIDQ581427zbMATH OpenFDO

Authors Vincent Bouchitté, M. 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

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

Recommendations

• NP-completeness results concerning greedy and super greedy linear extensions
• Greedy linear extensions to minimize jumps
• The number of depth-first searches of an ordered set
• Tackling the jump number of interval orders
• scientific article; zbMATH DE number 19350

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3641455 (Why is no real title available?)
• A decomposition theorem for partially ordered sets
• Algorithmic Approaches to Setup Minimization
• Minimizing Setups for Cycle-Free Ordered Sets
• NP-completeness results concerning greedy and super greedy linear extensions
• Optimal Linear Extensions by Interchanging Chains
• The Complexity of the Partial Order Dimension Problem
• The complexity of theorem-proving procedures

Cited in

(18)

• An improved approximation ratio for the jump number problem on interval orders
• Minimizing the sum cost in linear extensions of a poset
• A weighted version of the jump number problem on two-dimensional orders is NP-complete
• The setup polyhedron of series-parallel posets
• Computing the jump number on semi-orders is polynomial
• On the power of graph searching for cocomparability graphs
• The Shrinking Property for NP and coNP
• The jump number problem on interval orders: A 3/2 approximation algorithm
• A refined analysis on the jump number problem of interval orders
• An improved algorithm for the jump number problem
• NP-completeness results concerning greedy and super greedy linear extensions
• On a setup optimization problem for interval orders
• Tackling the jump number of interval orders
• The shrinking property for NP and coNP
• The arboreal jump number of an order
• A greedy reduction algorithm for setup optimization
• On Hardness of Multilinearization and VNP-Completeness in Characteristic 2
• On minimizing jumps for ordered sets

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q581427)