Approximating the maximum independent set and minimum vertex coloring on box graphs
(2007) Third International Conference, AAIM 2007 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:
https://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
 host publication
 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
 conference location
 Portland, OR, United States
 conference dates
 20070606  20070608
 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
 20160404 10:00:15
 date last changed
 20200112 21:07:43
@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}, doi = {10.1007/9783540728702_32}, volume = {4508}, year = {2007}, }