On the complexity of interval orders and semiorders
For an order \(P_ 0\), the \(P_ 0\)-recognition problem is to decide whether an unknown order is isomorphic to \(P_ 0\) by means of pairwise comparisons of the elements in the underlying set. The identification problem asks to determine an unknown order without a priori information. An order \(P\) is called an interval order whenever \(P\) does not contain the order \(2+2\) as an induced suborder. A semiorder is an interval order which does not contain the order \(1+3\) as an induced suborder. Questions: (a) Is the recognition complexity \(\Omega (n \log_ 2n)\) for every order on \(n\) elements? (b) Is there an optimal identification algorithm? Results: (a) \(\Omega (n \log_ 2n)\) is the recognition complexity of interval orders. (b) An optimal algorithm is given for the identification of semiorders.
- 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
- Representing interval orders by weighted bases: some complexity results
- Interval orders without odd crowns are defect optimal
- On the computational complexity of the order polynomial
- On relationships between numerical representations of interval orders and semiorders
- The communication complexity of interval orders
- Maximal sublattices of finite distributive lattices
- Compatibility between interval structures and partial orderings
- Tree-visibility orders
- On the complexity of partial order properties
- A recognition algorithm for orders of interval dimension two
- A characterization of interval orders with semiorder dimension two
- A genesis of interval orders and semiorders: transitive NaP-preferences
- scientific article; zbMATH DE number 512933 (Why is no real title available?)
- scientific article; zbMATH DE number 1985659 (Why is no real title available?)
- scientific article; zbMATH DE number 1533814 (Why is no real title available?)
- Linear orders and semiorders close to an interval order
- Inductive characterizations of finite interval orders and semiorders
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)
