Minimum vertex cover in rectangle graphs

DOI10.1016/J.COMGEO.2011.03.002zbMATH Open1225.05199OpenAlexW2030755759MaRDI QIDQ551504FDOQ551504

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

Recommendations

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

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)

Cites Work

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

Cited In (4)

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

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)