The Hardness of Approximating Poset Dimension
From MaRDI portal
Publication:3503501
DOI10.1016/j.endm.2007.07.084zbMath1341.06002OpenAlexW2013288868MaRDI QIDQ3503501
No author found.
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
Related Items (11)
Succinct posets ⋮ The hardness of approximating the boxicity, cubicity and threshold dimension of a graph ⋮ Graph classes with structured neighborhoods and algorithmic applications ⋮ The small inductive dimension of finite lattices through matrices ⋮ Topological Aspects of Matrix Abduction 2 ⋮ The Complexity of the Partial Order Dimension Problem: Closing the Gap ⋮ Semi-transitive orientations and word-representable graphs ⋮ Dimension preserving contractions and a finite list of 3-irreducible posets ⋮ Alternation Graphs ⋮ A study of the order dimension of a poset using matrices ⋮ MINING POSETS FROM LINEAR ORDERS
Cites Work
- On the ratio of optimal integral and fractional covers
- Zero knowledge and the chromatic number
- Dimension, graph and hypergraph coloring
- Fractional dimension of partial orders
- A decomposition theorem for partially ordered sets
- The Complexity of the Partial Order Dimension Problem
- A forbidden subposet characterization of an order — dimension inequality
- On the hardness of approximating minimization problems
- Partially Ordered Sets
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: The Hardness of Approximating Poset Dimension
