The complexity of embedding orders into small products of chains

DOI10.1007/s11083-009-9135-7zbMath1205.06001OpenAlexW1997873539MaRDI QIDQ603886

Éric Thierry, Olivier Raynaud

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 setsencodingsencoding dimensionproduct of chainsstring dimension

Mathematics Subject Classification ID

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

Related Items (4)

Succinct posets ⋮ Topological Aspects of Matrix Abduction 2 ⋮ The Secret Life of Keys: On the Calculation of Mechanical Lock Systems ⋮ Embedding ordered sets into distributive lattices

Cites Work

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

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