Subexponentialtime algorithms for maximum independent set and related problems on box graphs
(2003) 9th Annual International Conference, COCOON 2003 2697. p.5056 Abstract
 A box graph is the intersection graph of orthogonal rectangles in the plane. We consider such basic combinatorial problems on box graphs as maximum independent set, minimum vertex cover and maximum induced subgraph with polynomialtime testable hereditary property Pi. We show that they can be exactly solved in subexponential time, more precisely, in time 2(O(rootnlog n)), by applying Miller's simple cycle planar separator theorem [6] (in spite of the fact that the input box graph might be strongly nonplanar). Furthermore we extend our idea to include the intersection graphs of orthogonal dcubes of bounded aspect ratio and dimension. We present an algorithm that solves maximum independent set and the other aforementioned problems in time... (More)
 A box graph is the intersection graph of orthogonal rectangles in the plane. We consider such basic combinatorial problems on box graphs as maximum independent set, minimum vertex cover and maximum induced subgraph with polynomialtime testable hereditary property Pi. We show that they can be exactly solved in subexponential time, more precisely, in time 2(O(rootnlog n)), by applying Miller's simple cycle planar separator theorem [6] (in spite of the fact that the input box graph might be strongly nonplanar). Furthermore we extend our idea to include the intersection graphs of orthogonal dcubes of bounded aspect ratio and dimension. We present an algorithm that solves maximum independent set and the other aforementioned problems in time 2(O(d2dbn11/dlogn)) on, such box graphs in ddimensions. We do this by applying a separator theorem by Smith and Wormald [7]. Finally, we show that in general graph case substantially subexponential algorithms for maximum independent set and the maximum induced subgraph with polynomialtime testable hereditary property Pi problems can yield nontrivial upper bounds on approximation factors achievable in polynomial time. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/302300
 author
 Lingas, Andrzej ^{LU} and Wahlén, Martin ^{LU}
 organization
 publishing date
 2003
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 host publication
 Computing and combinatorics / Lecture notes in computer science
 volume
 2697
 pages
 50  56
 publisher
 Springer
 conference name
 9th Annual International Conference, COCOON 2003
 conference location
 Big Sky, MT, United States
 conference dates
 20030725  20030728
 external identifiers

 wos:000185044800007
 scopus:35248826866
 ISSN
 16113349
 03029743
 ISBN
 9783540405344
 DOI
 10.1007/3540450718_7
 language
 English
 LU publication?
 yes
 id
 f1e5aac0776c430480b974d41fe2a44e (old id 302300)
 date added to LUP
 20160401 11:58:31
 date last changed
 20210217 01:37:03
@inproceedings{f1e5aac0776c430480b974d41fe2a44e, abstract = {A box graph is the intersection graph of orthogonal rectangles in the plane. We consider such basic combinatorial problems on box graphs as maximum independent set, minimum vertex cover and maximum induced subgraph with polynomialtime testable hereditary property Pi. We show that they can be exactly solved in subexponential time, more precisely, in time 2(O(rootnlog n)), by applying Miller's simple cycle planar separator theorem [6] (in spite of the fact that the input box graph might be strongly nonplanar). Furthermore we extend our idea to include the intersection graphs of orthogonal dcubes of bounded aspect ratio and dimension. We present an algorithm that solves maximum independent set and the other aforementioned problems in time 2(O(d2dbn11/dlogn)) on, such box graphs in ddimensions. We do this by applying a separator theorem by Smith and Wormald [7]. Finally, we show that in general graph case substantially subexponential algorithms for maximum independent set and the maximum induced subgraph with polynomialtime testable hereditary property Pi problems can yield nontrivial upper bounds on approximation factors achievable in polynomial time.}, author = {Lingas, Andrzej and Wahlén, Martin}, booktitle = {Computing and combinatorics / Lecture notes in computer science}, isbn = {9783540405344}, issn = {16113349}, language = {eng}, pages = {5056}, publisher = {Springer}, title = {Subexponentialtime algorithms for maximum independent set and related problems on box graphs}, url = {http://dx.doi.org/10.1007/3540450718_7}, doi = {10.1007/3540450718_7}, volume = {2697}, year = {2003}, }