Sublinear approximation algorithms for boxicity and related problems

DOI10.1016/j.dam.2017.10.031zbMath1377.05183arXiv1505.04918OpenAlexW2963908004MaRDI QIDQ1693125

L. Sunil Chandran, Jasine Babu, Abhijin Adiga

Publication date: 11 January 2018

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

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

zbMATH Keywords

approximation algorithmparameterizationboxicitypartial order dimensionthreshold dimension

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Structural parameterizations for boxicity
• Ferrers dimension of grid intersection graphs
• On feedback vertex set: new measure and new structures
• The complexity ecology of parameters: An illustration using bounded max leaf number
• The relationship between the threshold dimension of split graphs and various dimensional parameters
• Cubicity, boxicity, and vertex cover
• Interval representations of planar graphs
• On the Ferrers dimension of a digraph
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A special planar satisfiability problem and a consequence of its NP- completeness
• Unit disk graph recognition is NP-hard
• Efficient graph representations
• Parameterized complexity of vertex colouring
• Computing crossing numbers in quadratic time
• Threshold graphs and related topics
• Proper interval vertex deletion
• Obtaining a planar graph by vertex deletion
• Boxicity and treewidth
• The Complexity of the Partial Order Dimension Problem: Closing the Gap
• Parameterized Algorithms for Boxicity
• Cubicity of interval graphs and the claw number
• Interval Completion Is Fixed Parameter Tractable
• Well-Quasi-Orders in Subclasses of Bounded Treewidth Graphs
• The Complexity of the Partial Order Dimension Problem
• On the Interplay Between Interval Dimension and Dimension
• Polynomial Time and Parameterized Approximation Algorithms for Boxicity
• Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation
• Boxicity and Poset Dimension