The hardness of approximating the boxicity, cubicity and threshold dimension of a graph

DOI10.1016/j.dam.2010.06.017zbMath1208.05140arXiv0903.1010OpenAlexW2091388992MaRDI QIDQ602742

L. Sunil Chandran, Diptendu Bhowmick, Abhijin Adiga

Publication date: 5 November 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0903.1010

zbMATH Keywords

split graphNP-completenessboxicityapproximation hardnesscubicitypartial order dimensionthreshold dimension

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Structural parameterizations for boxicity ⋮ Bounding threshold dimension: realizing graphic Boolean functions as the AND of majority gates ⋮ A constant factor approximation algorithm for boxicity of circular arc graphs ⋮ On the stab number of rectangle intersection graphs

Cites Work

• The relationship between the threshold dimension of split graphs and various dimensional parameters
• An upper bound for cubicity in terms of boxicity
• A special planar satisfiability problem and a consequence of its NP- completeness
• The Hardness of Approximating Poset Dimension
• The Complexity of the Partial Order Dimension Problem
• Partially Ordered Sets
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item