On the Complexity of Nonconvex Covering

DOI10.1137/0215031zbMATH Open0603.68103OpenAlexW2046559210MaRDI QIDQ3740282FDOQ3740282

Authors: Wolfgang Maass 

Publication date: 1986

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0215031

Recommendations

• scientific article; zbMATH DE number 4215407
• Fast approximation algorithms for a nonconvex covering problem
• Covering Polygons Is Hard
• NP-harte Probleme für minimale Polygonüberdeckungen. (NP-hard problems for minimal polygon coverings)
• On the computational complexity of optimization convex covering problems of graphs

zbMATH Keywords

computational geometryNP-completenessroboticspolynomial time algorithmdegree of nonconvexity

Mathematics Subject Classification ID

Computing methodologies and applications (68U99) Analysis of algorithms and problem complexity (68Q25) Polyhedra and polytopes; regular figures, division of spaces (51M20)

Cited In (4)

• The complexity of domination problems in circle graphs
• Location, pricing and the problem of Apollonius
• Title not available (Why is that?)
• Fast approximation algorithms for a nonconvex covering problem

This page was built for publication: On the Complexity of Nonconvex Covering

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