The complexity of embedding orders into small products of chains

DOI10.1007/S11083-009-9135-7MaRDI QIDQ603886zbMATH OpenOpenAlexFDO

Authors Olivier Raynaud, Eric Thierry

Publication date 8 November 2010

Published in Order (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11083-009-9135-7

zbMATH Keywords

optimizationcomputational complexitypartially ordered setsencoding dimensionencodingsproduct of chainsstring dimension

Mathematics Subject Classification ID

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

Recommendations

• Computational aspects of the 2-dimension of partially ordered sets
• Generalized Polychotomic Encoding: A Very Short Bit-Vector Encoding of Tree Hierarchies
• scientific article; zbMATH DE number 59573
• Drawing and encoding two-dimensional posets
• The complexity of the partial order dimension problem: closing the gap

Cites work

• scientific article; zbMATH DE number 2089399 (Why is no real title available?)
• scientific article; zbMATH DE number 3887060 (Why is no real title available?)
• scientific article; zbMATH DE number 3889592 (Why is no real title available?)
• scientific article; zbMATH DE number 3172309 (Why is no real title available?)
• scientific article; zbMATH DE number 3906537 (Why is no real title available?)
• scientific article; zbMATH DE number 3974960 (Why is no real title available?)
• scientific article; zbMATH DE number 53952 (Why is no real title available?)
• scientific article; zbMATH DE number 1016362 (Why is no real title available?)
• scientific article; zbMATH DE number 1554928 (Why is no real title available?)
• scientific article; zbMATH DE number 1554930 (Why is no real title available?)
• scientific article; zbMATH DE number 1554937 (Why is no real title available?)
• scientific article; zbMATH DE number 194916 (Why is no real title available?)
• scientific article; zbMATH DE number 6472574 (Why is no real title available?)
• scientific article; zbMATH DE number 3245483 (Why is no real title available?)
• An Efficient Data Structure for Lattice Operations
• An improved algorithm for transitive closure on acyclic digraphs
• Computational aspects of the 2-dimension of partially ordered sets
• Degrees of freedom versus dimension for containment orders
• Drawing and encoding two-dimensional posets
• Embedding finite posets in cubes
• Geometric containment orders: A survey
• On locally presented posets
• On the pseudodimension of ordered sets
• Partially Ordered Sets
• Partially Ordered Sets
• String realizers of posets with applications to distributed computing
• The Complexity of the Partial Order Dimension Problem
• The representation of posets and lattices by sets

Cited in

(9)

• Computational aspects of the 2-dimension of partially ordered sets
• Topological aspects of matrix abduction. II
• scientific article; zbMATH DE number 59573 (Why is no real title available?)
• The secret life of keys: on the calculation of mechanical lock systems
• Complexity of cover-preserving embeddings of bipartite orders into Boolean lattices
• Generalized Polychotomic Encoding: A Very Short Bit-Vector Encoding of Tree Hierarchies
• scientific article; zbMATH DE number 3863258 (Why is no real title available?)
• Succinct posets
• Embedding ordered sets into distributive lattices

This page was built for publication: The complexity of embedding orders into small products of chains

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