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)

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)