A note on maximum independent set and related problems on box graphs
(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:
https://lup.lub.lu.se/record/255305
- author
- Lingas, Andrzej LU and Wahlén, Martin LU
- organization
- publishing date
- 2005
- 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
- 2016-04-01 15:27:58
- date last changed
- 2022-01-28 05:27:12
@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}}, keywords = {{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}}, doi = {{10.1016/j.ipl.2004.10.013}}, volume = {{93}}, year = {{2005}}, }