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

DOI10.1007/BF02034331zbMath0683.06004OpenAlexW2030642203MaRDI QIDQ1824638

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

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

Related Items (1)

The Complexity of the Partial Order Dimension Problem: Closing the Gap

Cites Work

• Unnamed Item
• Edge subdivision and dimension
• Stacks and splits of partially ordered sets
• Some simplified NP-complete graph problems
• Dimension invariance of subdivisions
• The Complexity of the Partial Order Dimension Problem
• Optimal Linear Extensions by Interchanging Chains

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