Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Approximating the maximum independent set and minimum vertex coloring on box graphs

Han, Xin ; Iwama, Kazuo ; Klein, Rolf and Lingas, Andrzej LU (2007) Third International Conference, AAIM 2007 4508. p.337-345
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 sub-logarithmic 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 sub-logarithmic 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 d-dimensional 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:
author
; ; and
organization
publishing date
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
2007-06-06 - 2007-06-08
external identifiers
  • scopus:38149101680
ISBN
978-3-540-72868-9
DOI
10.1007/978-3-540-72870-2_32
project
VR 2005-4085
language
English
LU publication?
yes
id
a8627bbe-e14d-48a6-8eb4-e119241024b6 (old id 629555)
date added to LUP
2016-04-04 10:00:15
date last changed
2022-01-29 19:37:28
@inproceedings{a8627bbe-e14d-48a6-8eb4-e119241024b6,
  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 sub-logarithmic 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 d-dimensional 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         = {{978-3-540-72868-9}},
  language     = {{eng}},
  pages        = {{337--345}},
  publisher    = {{Springer}},
  title        = {{Approximating the maximum independent set and minimum vertex coloring on box graphs}},
  url          = {{http://dx.doi.org/10.1007/978-3-540-72870-2_32}},
  doi          = {{10.1007/978-3-540-72870-2_32}},
  volume       = {{4508}},
  year         = {{2007}},
}