Approximating the maximum independent set and minimum vertex coloring on box graphs
(2007) Third International Conference, AAIM 2007 In Algorithmic Aspects in Information and Management / Lecture Notes in Computer Science 4508. p.337345 Abstract
 A box graph is the intersection graph of a finite set of orthogonal rectangles in the plane. The problem of whether or not the maximum independent set problem (MIS for short) for box graphs can be approximated within a substantially sublogarithmic factor in polynomial time has been open for several years. We show that for box graphs on n vertices which have an independent set of size Ω(n/logO(1)n) the maximum independent set problem can be approximated within O(logn / loglogn) in polynomial time. Furthermore, we show that the chromatic number of a box graph on n vertices is within an O(logn) factor from the size of its maximum clique and provide an O(logn) approximation algorithm for minimum vertex coloring of such a box graph. More... (More)
 A box graph is the intersection graph of a finite set of orthogonal rectangles in the plane. The problem of whether or not the maximum independent set problem (MIS for short) for box graphs can be approximated within a substantially sublogarithmic factor in polynomial time has been open for several years. We show that for box graphs on n vertices which have an independent set of size Ω(n/logO(1)n) the maximum independent set problem can be approximated within O(logn / loglogn) in polynomial time. Furthermore, we show that the chromatic number of a box graph on n vertices is within an O(logn) factor from the size of its maximum clique and provide an O(logn) approximation algorithm for minimum vertex coloring of such a box graph. More generally, we can show that the chromatic number of the intersection graph of n ddimensional orthogonal rectangles is within an O(logd − 1n) factor from the size of its maximum clique and obtain an O(logd − 1n) approximation algorithm for minimum vertex coloring of such an intersection graph. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/629555
 author
 Han, Xin; Iwama, Kazuo; Klein, Rolf and Lingas, Andrzej ^{LU}
 organization
 publishing date
 2007
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 in
 Algorithmic Aspects in Information and Management / Lecture Notes in Computer Science
 volume
 4508
 pages
 337  345
 publisher
 Springer
 conference name
 Third International Conference, AAIM 2007
 external identifiers

 scopus:38149101680
 ISBN
 9783540728689
 DOI
 10.1007/9783540728702_32
 project
 VR 20054085
 language
 English
 LU publication?
 yes
 id
 a8627bbee14d48a68eb4e119241024b6 (old id 629555)
 date added to LUP
 20071127 14:34:15
 date last changed
 20180107 10:29:49
@inproceedings{a8627bbee14d48a68eb4e119241024b6, abstract = {A box graph is the intersection graph of a finite set of orthogonal rectangles in the plane. The problem of whether or not the maximum independent set problem (MIS for short) for box graphs can be approximated within a substantially sublogarithmic factor in polynomial time has been open for several years. We show that for box graphs on n vertices which have an independent set of size Ω(n/logO(1)n) the maximum independent set problem can be approximated within O(logn / loglogn) in polynomial time. Furthermore, we show that the chromatic number of a box graph on n vertices is within an O(logn) factor from the size of its maximum clique and provide an O(logn) approximation algorithm for minimum vertex coloring of such a box graph. More generally, we can show that the chromatic number of the intersection graph of n ddimensional orthogonal rectangles is within an O(logd − 1n) factor from the size of its maximum clique and obtain an O(logd − 1n) approximation algorithm for minimum vertex coloring of such an intersection graph.}, author = {Han, Xin and Iwama, Kazuo and Klein, Rolf and Lingas, Andrzej}, booktitle = {Algorithmic Aspects in Information and Management / Lecture Notes in Computer Science}, isbn = {9783540728689}, language = {eng}, pages = {337345}, publisher = {Springer}, title = {Approximating the maximum independent set and minimum vertex coloring on box graphs}, url = {http://dx.doi.org/10.1007/9783540728702_32}, volume = {4508}, year = {2007}, }