A constant factor approximation algorithm for boxicity of circular arc graphs
type: Item
instance of: scholarly article
title: A constant factor approximation algorithm for boxicity of circular arc graphs
zbMATH Open document ID: 1300.05188
author: Abhijin Adiga
author: Jasine Babu
author: L. Sunil Chandran
published in: Discrete Applied Mathematics
publication date: 2014-09-12T00:00:00Z
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 6343740
zbMATH Keywords: boxicity
zbMATH Keywords: cubicity
zbMATH Keywords: circular arc graphs
zbMATH Keywords: approximation algorithm
zbMATH Keywords: normal circular arc graphs
MaRDI profile type: Publication
full work available at URL: j.dam.2014.06.013
OpenAlex ID: W2055852904
cites work: A min-max property of chordal bipartite graphs with applications
cites work: The hardness of approximating the boxicity, cubicity and threshold dimension of a graph
cites work: Boxicity and Poset Dimension
cites work: Grid intersection graphs and boxicity
cites work: Finding a maximum induced matching in weakly chordal graphs
cites work: Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation
cites work: Cubicity, boxicity, and vertex cover
cites work: An upper bound for cubicity in terms of boxicity
cites work: Boxicity and treewidth
cites work: Boxicity of graphs with bounded degree
cites work: List homomorphisms and circular arc graphs
cites work: Contact representations of planar graphs with cubes
cites work: The Complexity of Coloring Circular Arcs and Chords
cites work: New results on induced matchings
cites work: A special planar satisfiability problem and a consequence of its NP- completeness
cites work: Characterizations and recognition of circular-arc graphs and subclasses: a survey
cites work: Q4407446
cites work: The Branch-Width of Circular-Arc Graphs
cites work: Linear-time recognition of circular-arc graphs
cites work: Characterization of the graphs with boxicity \(\leq 2\)
cites work: Q5588433
cites work: Q5387691
cites work: On orthogonal ray graphs
cites work: Pathwidth of Circular-Arc Graphs
cites work: Treewidth of Circular-Arc Graphs
cites work: Interval representations of planar graphs
cites work: A characterization of Robert's inequality for boxicity
cites work: Matrix characterizations of circular-arc graphs
cites work: Structure theorems for some circular-arc graphs
cites work: An Efficient Test for Circular-Arc Graphs
cites work: The Complexity of the Partial Order Dimension Problem
cites work: On the complexity of the k-chain subgraph cover problem
DOI: 10.1016/J.DAM.2014.06.013
Recommended article: A Constant Factor Approximation Algorithm for Boxicity of Circular Arc Graphs
Recommended article: Boxicity of circular arc graphs
Recommended article: Q4511218
Recommended article: Linear time algorithms on circular-arc graphs
Recommended article: Hamilton cycles in split graphs with large minimum degree
Recommended article: Properties of an approximability-related parameter on circular complete graphs
Recommended article: A linear-time algorithm for paired-domination on circular-arc graphs
Recommended article: Polynomial time algorithms on circular-arc overlap graphs
Recommended article: Q4028894
Recommended article: Efficient and perfect domination on circular-arc graphs
description: scientific article; zbMATH DE number 6343740