On the computational complexity of the order polynomial

DOI10.1016/0166-218X(86)90047-8MaRDI QIDQ1086595zbMATH OpenFDO

Authors U. Faigle, Rainer Schrader

Publication date 1986

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(86)90047-8

zbMATH Keywords

computational complexityorder polynomialorders with bounded widthpolynomial timesemiordersseries-parallel orders

Mathematics Subject Classification ID

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

Review text

Efficient algorithms for computing the order polynomial for the classes of orders with bounded width and series-parallel orders are presented. It is proved that for any fixed i the i-th coefficient of the order polynomial can be computed in polynomial time for the class of semiorders.

Recommendations

• scientific article; zbMATH DE number 4027523
• Computing the jump number on semi-orders is polynomial
• scientific article; zbMATH DE number 512933
• On the complexity of interval orders and semiorders
• scientific article; zbMATH DE number 4041286

Cites work

• A Brylawski decomposition for finite ordered sets
• Acyclic orientations of graphs
• Combinatorial theory.
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• Measurement Theory
• On some complexity properties of N-free posets and posets with bounded decomposition diameter
• Ordered structures and partitions
• Searching in Trees, Series-Parallel and Interval Orders
• Single Machine Scheduling with Precedence Constraints of Dimension 2
• Some Colouring Problems and their Complexity
• The complexity of computing the permanent
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected

Cited in

(7)

• Cross-series-parallel digraphs
• Many order types on integer grids of polynomial size
• An algebra over the operad of posets and structural binomial identities
• Doppelgangers: the ur-operation and posets of bounded height (extended abstract)
• scientific article; zbMATH DE number 4027523 (Why is no real title available?)
• scientific article; zbMATH DE number 14735 (Why is no real title available?)
• Query order in the polynomial hierarchy

This page was built for publication: On the computational complexity of the order polynomial

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