The Hardness of Approximating Poset Dimension

DOI10.1016/J.ENDM.2007.07.084MaRDI QIDQ3503501zbMATH OpenOpenAlexFDO

Authors

Publication date 5 June 2008

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2007.07.084

zbMATH Keywords

partially ordered setsposet dimension

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07)

Recommendations

• On an extremal problem for poset dimension
• A Poset Dimension Algorithm
• The Complexity of the Extendibility Problem for Finite Posets
• The dimension of posets with planar cover graphs.
• A note on the dimension of a poset
• scientific article; zbMATH DE number 4118416
• On dimension of poset variety
• Dimension, Halfspaces, and the Density of Hard Sets
• Dimension, halfspaces, and the density of hard sets
• Better bounds for poset dimension and boxicity

Cites work

• scientific article; zbMATH DE number 53952 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1028228 (Why is no real title available?)
• scientific article; zbMATH DE number 1161251 (Why is no real title available?)
• scientific article; zbMATH DE number 1554930 (Why is no real title available?)
• scientific article; zbMATH DE number 3318595 (Why is no real title available?)
• A decomposition theorem for partially ordered sets
• A forbidden subposet characterization of an order — dimension inequality
• Dimension, graph and hypergraph coloring
• Fractional dimension of partial orders
• On the hardness of approximating minimization problems
• On the ratio of optimal integral and fractional covers
• Partially Ordered Sets
• The Complexity of the Partial Order Dimension Problem
• Zero knowledge and the chromatic number

Cited in

(13)

• The hardness of approximating the boxicity, cubicity and threshold dimension of a graph
• Topological aspects of matrix abduction. II
• Graph classes with structured neighborhoods and algorithmic applications
• Succinct posets
• Edge subdivision and dimension
• The complexity of the partial order dimension problem: closing the gap
• A study of the order dimension of a poset using matrices
• Semi-transitive orientations and word-representable graphs
• Mining posets from linear orders.
• The small inductive dimension of finite lattices through matrices
• Fractional dimension of partial orders
• Alternation graphs
• Dimension preserving contractions and a finite list of 3-irreducible posets

This page was built for publication: The Hardness of Approximating Poset Dimension

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