Minimum vertex cover in rectangle graphs

DOI10.1016/J.COMGEO.2011.03.002MaRDI QIDQ551504zbMATH OpenOpenAlexFDO

Authors 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) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Minimum vertex cover in rectangle graphs
• Experimental and Efficient Algorithms
• scientific article; zbMATH DE number 5291457
• An algorithm for covering polygons with rectangles
• A note on maximum independent sets in rectangle intersection graphs

Cites work

• scientific article; zbMATH DE number 3889282 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3750313 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1303579 (Why is no real title available?)
• scientific article; zbMATH DE number 1330032 (Why is no real title available?)
• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 867674 (Why is no real title available?)
• scientific article; zbMATH DE number 1424290 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A decomposition theorem for partially ordered sets
• A linear-time approximation algorithm for the weighted vertex cover problem
• A note on maximum independent sets in rectangle intersection graphs
• Admission control in networks with advance reservations
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Algorithms – ESA 2005
• Applications of a Planar Separator Theorem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation algorithms for NP-hard problems.
• Approximation algorithms for maximum independent set of pseudo-disks
• Approximation hardness of optimization problems in intersection graphs of \(d\)-dimensional boxes
• Approximation schemes for covering and packing problems in image processing and VLSI
• Automata, Languages and Programming
• Better Approximation Schemes for Disk Graphs
• Efficient approximation algorithms for tiling and packing problems with rectangles
• Graph minors. II. Algorithmic aspects of tree-width
• Graph-Theoretic Concepts in Computer Science
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• Label placement by maximum independent set in rectangles
• Linear time algorithms on circular-arc graphs
• Maximum independent set and maximum clique algorithms for overlap graphs
• Maximum independent set of rectangles
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• New clique and independent set algorithms for circle graphs
• Optimal packing and covering in the plane are NP-complete
• Optimization problems in multiple-interval graphs
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Polynomial-time approximation schemes for packing and piercing fat objects
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• Reducibility among combinatorial problems
• Scheduling Split Intervals
• Stability in circular arc graphs
• The importance of being biased
• Vertex packings: Structural properties and algorithms

Cited in

(4)

• On dominating set of some subclasses of string graphs
• Minimum vertex cover in rectangle graphs
• Optimization problems in dotted interval graphs
• Packing and covering with non-piercing regions

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q551504)