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)

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

zbMATH Keywords

depth-first greedy linear extensionsDilworth partially ordered setsDilworth posetsjump number problemNP-completenessNP-hard

Mathematics Subject Classification ID

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

Review text

The authors present ``some complexity results about the construction of depth-first greedy linear extensions. They prove ``that the recognition of Dilworth partially ordered sets of height 2, as defined by Sysło, is NP-complete. This last result yields a new proof of the NP-completeness of the jump number problem, first proved by Pulleyblank. The following theorems are presented: Theorem 1. Not depth-first greedy is NP-complete. Theorem 2. Weakly depth-first greedy is NP-hard. Theorem 3. Recognition of Dilworth posets is NP-complete. Corollary. The jump number is NP-hard.

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

• A decomposition theorem for partially ordered sets
• Algorithmic Approaches to Setup Minimization
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3641455 (Why is no real title available?)
• 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

(20)

• NP-completeness results concerning greedy and super greedy linear extensions
• 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
• A weighted version of the jump number problem on two-dimensional orders is NP-complete
• An improved algorithm for the jump number problem
• The jump number problem on interval orders: A 3/2 approximation algorithm
• The arboreal jump number of an order
• A refined analysis on the jump number problem of interval orders
• On the power of graph searching for cocomparability graphs
• The Shrinking Property for NP and coNP
• An improved approximation ratio for the jump number problem on interval orders
• scientific article; zbMATH DE number 637537 (Why is no real title available?)
• On Hardness of Multilinearization and VNP-Completeness in Characteristic 2
• The shrinking property for NP and coNP
• Minimizing the sum cost in linear extensions of a poset
• Width notions for ordering-related problems

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)