The complexity of embedding orders into small products of chains

DOI10.1007/S11083-009-9135-7zbMATH Open1205.06001OpenAlexW1997873539MaRDI QIDQ603886FDOQ603886

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Degrees of freedom versus dimension for containment orders
• Title not available (Why is that?)
• The Complexity of the Partial Order Dimension Problem
• Title not available (Why is that?)
• Partially Ordered Sets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• String realizers of posets with applications to distributed computing
• An Efficient Data Structure for Lattice Operations
• Title not available (Why is that?)
• On locally presented posets
• Partially Ordered Sets
• Title not available (Why is that?)
• Embedding finite posets in cubes
• An improved algorithm for transitive closure on acyclic digraphs
• The representation of posets and lattices by sets
• Geometric containment orders: A survey
• Drawing and encoding two-dimensional posets
• Computational aspects of the 2-dimension of partially ordered sets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the pseudodimension of ordered sets

Cited In (9)

• Title not available (Why is that?)
• The secret life of keys: on the calculation of mechanical lock systems
• Embedding ordered sets into distributive lattices
• Topological aspects of matrix abduction. II
• Succinct posets
• Computational aspects of the 2-dimension of partially ordered sets
• Title not available (Why is that?)
• Generalized Polychotomic Encoding: A Very Short Bit-Vector Encoding of Tree Hierarchies
• Complexity of cover-preserving embeddings of bipartite orders into Boolean 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)