On the complexity of interval orders and semiorders

DOI10.1016/0012-365X(87)90003-3MaRDI QIDQ1088407zbMATH OpenFDO

Authors U. Faigle, Gy. Turán

Publication date 1987

Published in Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

computational complexityidentification probleminterval ordersemiorderrecognition complexityoptimal identification algorithmorder recognition problem

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 512933
• On the complexity of partial order properties
• Limits of interval orders and semiorders
• On relationships between numerical representations of interval orders and semiorders
• A partial order structure on interval orders
• Interval orders, semiorders and ordered groups
• A generalization of interval orders
• Inductive characterizations of finite interval orders and semiorders

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3909755 (Why is no real title available?)
• Measurement Theory

Cited in

(16)

• On the computational complexity of the order polynomial
• Inductive characterizations of finite interval orders and semiorders
• Maximal sublattices of finite distributive lattices
• A characterization of interval orders with semiorder dimension two
• Tree-visibility orders
• On the complexity of partial order properties
• scientific article; zbMATH DE number 1985659 (Why is no real title available?)
• Compatibility between interval structures and partial orderings
• scientific article; zbMATH DE number 1533814 (Why is no real title available?)
• Representing interval orders by weighted bases: some complexity results
• A recognition algorithm for orders of interval dimension two
• On relationships between numerical representations of interval orders and semiorders
• Linear orders and semiorders close to an interval order
• The communication complexity of interval orders
• Interval orders without odd crowns are defect optimal
• A genesis of interval orders and semiorders: transitive NaP-preferences

This page was built for publication: On the complexity of interval orders and semiorders

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