Minimum vertex cover in rectangle graphs

DOI10.1016/j.comgeo.2011.03.002zbMath1225.05199OpenAlexW2030755759MaRDI QIDQ551504

Danny Hermelin, Dror Rawitz, Reuven Bar Yehuda

Publication date: 20 July 2011

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2011.03.002

zbMATH Keywords

approximation algorithmsintersection graphsarrangement graphsaxis-parallel rectanglespseudo-disks

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)

Related Items (3)

On dominating set of some subclasses of string graphs ⋮ Optimization problems in dotted interval graphs ⋮ Packing and covering with non-piercing regions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• A note on maximum independent sets in rectangle intersection graphs
• Optimal packing and covering in the plane are NP-complete
• Linear time algorithms on circular-arc graphs
• New clique and independent set algorithms for circle graphs
• Label placement by maximum independent set in rectangles
• Maximum independent set and maximum clique algorithms for overlap graphs
• Admission control in networks with advance reservations
• A decomposition theorem for partially ordered sets
• Efficient Approximation Algorithms for Tiling and Packing Problems with Rectangles
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• The importance of being biased
• Graph minors. II. Algorithmic aspects of tree-width
• Approximation schemes for covering and packing problems in image processing and VLSI
• Stability in circular arc graphs
• Applications of a Planar Separator Theorem
• A linear-time approximation algorithm for the weighted vertex cover problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Vertex packings: Structural properties and algorithms
• Approximation algorithms for NP-complete problems on planar graphs
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Polynomial-time approximation schemes for packing and piercing fat objects
• Reducibility among Combinatorial Problems
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Approximation algorithms for maximum independent set of pseudo-disks
• Scheduling Split Intervals
• Algorithms – ESA 2005
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Automata, Languages and Programming
• Better Approximation Schemes for Disk Graphs
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Minimum vertex cover in rectangle graphs