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

Summary, in English

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.

• Författare: Xin Han; Kazuo Iwama; Rolf Klein; Andrzej Lingas
• Avdelning/ar: Computer Science
• Publiceringsår: 2007
• Språk: Engelska
• Sidor: 337-345
• Publikation/Tidskrift/Serie: Algorithmic Aspects in Information and Management / Lecture Notes in Computer Science
• Volym: 4508
• Länkar: http://dx.doi.org/10.1007/978-3-540-72870-2_32
• Dokumenttyp: Konferensbidrag
• Förlag: Springer
• Ämne: Computer Science
• Conference name: Third International Conference, AAIM 2007
• Conference date: 2007-06-06 - 2007-06-08
• Conference place: Portland, OR, United States
• Status: Published
• Projekt: VR 2005-4085
• ISBN/ISSN/Övrigt: ISBN: 978-3-540-72868-9