Minimum Vertex Cover in Rectangle Graphs

Minimum Vertex Cover in Rectangle Graphs,10.1007/978-3-642-15775-2_22,Computing Research Repository,Reuven Bar-Yehuda,Danny Hermelin,Dror Rawitz

Minimum Vertex Cover in Rectangle Graphs   (Citations: 1)
BibTex | RIS | RefWorks Download
We consider the Minimum Vertex Cover problem in intersection graphs of axis-parallel rectangles on the plane. We present two algorithms: The first is an EPTAS for non-crossing rectangle families, rectangle families R where R1 \ R2 is connected for every pair of rectangles R1, R2 2 R. The second algorithm achieves a factor of (1.5 + ") in general rectangle families, for any fixed " > 0, and works also for the weighted variant of the problem. Both algorithms exploit the plane properties of axis-parallel rectangles in a non-trivial way.
Journal: Computing Research Repository - CORR , vol. abs/1001.3, pp. 255-266, 2010
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: