On the computational complexity of the order polynomial

DOI10.1016/0166-218X(86)90047-8zbMath0609.06001MaRDI QIDQ1086595

Rainer Schrader, Ulrich Faigle

Publication date: 1986

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

zbMATH Keywords

computational complexitypolynomial timesemiordersorder polynomialorders with bounded widthseries-parallel orders

Mathematics Subject Classification ID

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

Related Items (3)

Doppelgangers: the ur-operation and posets of bounded height (extended abstract) ⋮ Cross-series-parallel digraphs ⋮ An algebra over the operad of posets and structural binomial identities

Cites Work

• Unnamed Item
• The complexity of computing the permanent
• On some complexity properties of N-free posets and posets with bounded decomposition diameter
• A Brylawski decomposition for finite ordered sets
• Acyclic orientations of graphs
• Combinatorial theory.
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Single Machine Scheduling with Precedence Constraints of Dimension 2
• Searching in Trees, Series-Parallel and Interval Orders
• Some Colouring Problems and their Complexity
• Ordered structures and partitions
• Measurement Theory

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