Advanced

A note on maximum independent set and related problems on box graphs

Lingas, Andrzej LU and Wahlén, Martin LU (2005) In Information Processing Letters 93(4). p.169-171
Abstract
A box graph is the intersection graph of orthogonal rectangles in the plane. We show that maximum independent set and minimum vertex cover on box graphs can be solved in subexponential time, more precisely, in time 2(O(rootn log n)), by applying Miller's simple cycle planar separator theorem [J. Comput. System Sci. 32 (1986) 265-279] (in spite of the fact that the input box graph might be strongly non-planar).
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
algorithms, analysis of algorithms, complexity
in
Information Processing Letters
volume
93
issue
4
pages
169 - 171
publisher
Elsevier
external identifiers
  • wos:000226402500003
  • scopus:25444520764
ISSN
0020-0190
DOI
10.1016/j.ipl.2004.10.013
language
English
LU publication?
yes
id
e01f7c7f-759c-4949-b46a-b46fa8091deb (old id 255305)
date added to LUP
2007-08-03 13:39:01
date last changed
2017-01-01 06:40:13
@article{e01f7c7f-759c-4949-b46a-b46fa8091deb,
  abstract     = {A box graph is the intersection graph of orthogonal rectangles in the plane. We show that maximum independent set and minimum vertex cover on box graphs can be solved in subexponential time, more precisely, in time 2(O(rootn log n)), by applying Miller's simple cycle planar separator theorem [J. Comput. System Sci. 32 (1986) 265-279] (in spite of the fact that the input box graph might be strongly non-planar).},
  author       = {Lingas, Andrzej and Wahlén, Martin},
  issn         = {0020-0190},
  keyword      = {algorithms,analysis of algorithms,complexity},
  language     = {eng},
  number       = {4},
  pages        = {169--171},
  publisher    = {Elsevier},
  series       = {Information Processing Letters},
  title        = {A note on maximum independent set and related problems on box graphs},
  url          = {http://dx.doi.org/10.1016/j.ipl.2004.10.013},
  volume       = {93},
  year         = {2005},
}