Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6872135 | Discrete Applied Mathematics | 2014 | 18 Pages |
Abstract
In this paper, we consider the problem of approximating the boxicity (cubicity) of circular arc graphs-intersection graphs of arcs of a circle. Circular arc graphs are known to have unbounded boxicity, which could be as large as Ω(n). We give a (2+1k)-factor (resp.(2+âlognâk)-factor) polynomial time approximation algorithm for computing the boxicity (resp. cubicity) of any circular arc graph, where kâ¥1 is the value of the optimum solution. For normal circular arc (NCA) graphs, with an NCA model given, this can be improved to an additive two approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity (resp. cubicity) is O(mn+n2) in both these cases, and in O(mn+kn2)=O(n3) time we also get their corresponding box (resp. cube) representations, where n is the number of vertices of the graph and m is its number of edges. Our additive two approximation algorithm directly works for any proper circular arc graph, since their NCA models can be computed in polynomial time.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Abhijin Adiga, Jasine Babu, L. Sunil Chandran,