Computational aspects of the 2-dimension of partially ordered sets

DOI10.1016/j.tcs.2003.10.029zbMath1070.68051OpenAlexW2079868952MaRDI QIDQ1884957

Lhouari Nourine, Éric Thierry, Olivier Raynaud, Michel A. Habib

Publication date: 27 October 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2003.10.029

zbMATH Keywords

computational complexity

Mathematics Subject Classification ID

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

Related Items

2-dimension from the topological viewpoint, The complexity of embedding orders into small products of chains, Topological Aspects of Matrix Abduction 2, Edge cover by connected bipartite subgraphs, The Secret Life of Keys: On the Calculation of Mechanical Lock Systems, Generalized Polychotomic Encoding: A Very Short Bit-Vector Encoding of Tree Hierarchies

Cites Work

• The jump number and the lattice of maximal antichains
• Bipartite dimensions and bipartite degrees of graphs
• The representation of posets and lattices by sets
• Embedding finite posets in cubes
• Simplicial elimination schemes, extremal lattices and maximal antichain lattices
• On the order dimension of 1-sets versus \(k\)-sets
• On edge perfectness and classes of bipartite graphs
• On Approximate Solutions for Combinatorial Optimization Problems
• The Recognition of Series Parallel Digraphs
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• On the pseudodimension of 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