Computational aspects of the 2-dimension of partially ordered sets

DOI10.1016/J.TCS.2003.10.029MaRDI QIDQ1884957zbMATH OpenOpenAlexFDO

Authors Lhouari Nourine, M. A. Habib, Olivier Raynaud, Eric Thierry

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

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

Recommendations

• Generalized Polychotomic Encoding: A Very Short Bit-Vector Encoding of Tree Hierarchies
• Drawing and encoding two-dimensional posets
• The complexity of embedding orders into small products of chains
• scientific article; zbMATH DE number 1554928
• 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 3172309 (Why is no real title available?)
• scientific article; zbMATH DE number 3974960 (Why is no real title available?)
• scientific article; zbMATH DE number 3984613 (Why is no real title available?)
• scientific article; zbMATH DE number 4073041 (Why is no real title available?)
• scientific article; zbMATH DE number 3771669 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 736305 (Why is no real title available?)
• scientific article; zbMATH DE number 1016362 (Why is no real title available?)
• scientific article; zbMATH DE number 1161251 (Why is no real title available?)
• scientific article; zbMATH DE number 1554928 (Why is no real title available?)
• scientific article; zbMATH DE number 194916 (Why is no real title available?)
• scientific article; zbMATH DE number 3232102 (Why is no real title available?)
• Bipartite dimensions and bipartite degrees of graphs
• Embedding finite posets in cubes
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• On Approximate Solutions for Combinatorial Optimization Problems
• On edge perfectness and classes of bipartite graphs
• On the order dimension of 1-sets versus \(k\)-sets
• On the pseudodimension of ordered sets
• Partially Ordered Sets
• Simplicial elimination schemes, extremal lattices and maximal antichain lattices
• The Recognition of Series Parallel Digraphs
• The jump number and the lattice of maximal antichains
• The representation of posets and lattices by sets

Cited in

(8)

• Topological aspects of matrix abduction. II
• 2-dimension from the topological viewpoint
• The secret life of keys: on the calculation of mechanical lock systems
• Edge cover by connected bipartite subgraphs
• Generalized Polychotomic Encoding: A Very Short Bit-Vector Encoding of Tree Hierarchies
• The complexity of embedding orders into small products of chains
• scientific article; zbMATH DE number 4025488 (Why is no real title available?)
• scientific article; zbMATH DE number 1554928 (Why is no real title available?)

This page was built for publication: Computational aspects of the 2-dimension of partially ordered sets

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