Minimum Vertex Cover in Rectangle Graphs

Details Minimum Vertex Cover in Rectangle Graphs Minimum Vertex Cover in Rectangle Graphs

2010-01-19

arxiv.org/abs/1001.3332v1

Computer Science

Data Structures and Algorithms

Scientific paper

We consider the 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 $\calR$ where $R_1 \setminus R_2$ is connected for every pair of rectangles $R_1,R_2 \in \calR$. This algorithm extends to intersection graphs of pseudo-disks. The second algorithm achieves a factor of $(1.5 + \varepsilon)$ in general rectangle families, for any fixed $\varepsilon > 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.

Affiliated with

Also associated with

No associations

Rating

Minimum Vertex Cover in Rectangle Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Minimum Vertex Cover in Rectangle Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum Vertex Cover in Rectangle Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-636745