Computing the dimension of N-free ordered sets is NP-complete

DOI10.1007/BF02034331MaRDI QIDQ1824638zbMATH OpenOpenAlexFDO

Authors H. A. Kiersteat, S. G. Penrice

Publication date 1989

Published in Order (Search for Journal in Brave)

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

zbMATH Keywords

dimensionNP-completeN-free ordered set

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 6157242 (Why is no real title available?)
• Dimension invariance of subdivisions
• Edge subdivision and dimension
• Optimal Linear Extensions by Interchanging Chains
• Some simplified NP-complete graph problems
• Stacks and splits of partially ordered sets
• The Complexity of the Partial Order Dimension Problem

Cited in

(3)

• Contiguity orders
• The complexity of the partial order dimension problem: closing the gap
• On some complexity properties of N-free posets and posets with bounded decomposition diameter

This page was built for publication: Computing the dimension of N-free ordered sets is NP-complete

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