A constant factor approximation algorithm for boxicity of circular arc graphs
From MaRDI portal
Publication:741528
DOI10.1016/j.dam.2014.06.013zbMath1300.05188MaRDI QIDQ741528
L. Sunil Chandran, Abhijin Adiga, Jasine Babu
Publication date: 12 September 2014
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2014.06.013
68W25: Approximation algorithms
05C62: Graph representations (geometric and intersection representations, etc.)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On orthogonal ray graphs
- The hardness of approximating the boxicity, cubicity and threshold dimension of a graph
- Grid intersection graphs and boxicity
- Boxicity of graphs with bounded degree
- Cubicity, boxicity, and vertex cover
- An upper bound for cubicity in terms of boxicity
- Characterizations and recognition of circular-arc graphs and subclasses: a survey
- Interval representations of planar graphs
- A characterization of Robert's inequality for boxicity
- On the complexity of the k-chain subgraph cover problem
- A special planar satisfiability problem and a consequence of its NP- completeness
- Linear-time recognition of circular-arc graphs
- Finding a maximum induced matching in weakly chordal graphs
- A min-max property of chordal bipartite graphs with applications
- New results on induced matchings
- List homomorphisms and circular arc graphs
- Characterization of the graphs with boxicity \(\leq 2\)
- Matrix characterizations of circular-arc graphs
- Structure theorems for some circular-arc graphs
- Boxicity and treewidth
- Pathwidth of Circular-Arc Graphs
- The Branch-Width of Circular-Arc Graphs
- The Complexity of the Partial Order Dimension Problem
- An Efficient Test for Circular-Arc Graphs
- The Complexity of Coloring Circular Arcs and Chords
- Treewidth of Circular-Arc Graphs
- Contact representations of planar graphs with cubes
- Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation
- Boxicity and Poset Dimension
