Approximability issues of guarding a set of segments

DOI10.1080/00207160.2013.775423zbMath1279.90141OpenAlexW1990736088MaRDI QIDQ2855782

Valentin E. Brimkov

Publication date: 22 October 2013

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207160.2013.775423

zbMATH Keywords

approximation algorithmvertex coverset coverNP-complete problemguarding a set of segments

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (3)

Geometric hitting set for segments of few orientations ⋮ Graphs with equal domination and covering numbers ⋮ Intersections and circuits in sets of line segments

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation algorithms for a geometric set cover problem
• Guarding a set of line segments in the plane
• Solving NP-hard problems in 'almost trees': vertex cover
• Uniform random number generation
• Algorithms for Reporting and Counting Geometric Intersections
• Experimental Study on Approximation Algorithms for Guarding Sets of Line Segments
• A threshold of ln n for approximating set cover
• Solving NP-Hard Problems on Graphs That Are Almost Trees and an Application to Facility Location Problems
• On the hardness of approximating minimization problems
• Finding All the Elementary Circuits of a Directed Graph
• On the Number of Husimi Trees

This page was built for publication: Approximability issues of guarding a set of segments