Minimum Vertex Cover in Rectangle Graphs
Copyright policy )Minimum Vertex Cover in Rectangle Graphs
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.
- Tel Aviv University Israel
- Max Planck Society Germany
- Technion – Israel Institute of Technology Israel
- Max Planck Institute for Informatics Germany
Computational Geometry (cs.CG), FOS: Computer and information sciences, Intersection graphs, Arrangement graphs, Control and Optimization, Pseudo-disks, Planar graphs; geometric and topological aspects of graph theory, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), approximation algorithms, Extremal problems in graph theory, arrangement graphs, intersection graphs, Approximation algorithms, axis-parallel rectangles, Computer Science Applications, Computational Mathematics, Computational Theory and Mathematics, Axis-parallel rectangles, Computer Science - Computational Geometry, Geometry and Topology, pseudo-disks
Computational Geometry (cs.CG), FOS: Computer and information sciences, Intersection graphs, Arrangement graphs, Control and Optimization, Pseudo-disks, Planar graphs; geometric and topological aspects of graph theory, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), approximation algorithms, Extremal problems in graph theory, arrangement graphs, intersection graphs, Approximation algorithms, axis-parallel rectangles, Computer Science Applications, Computational Mathematics, Computational Theory and Mathematics, Axis-parallel rectangles, Computer Science - Computational Geometry, Geometry and Topology, pseudo-disks
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).5 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!