On the Complexity of Nonconvex Covering

DOI10.1137/0215031MaRDI QIDQ3740282zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

computational geometrydegree of nonconvexityNP-completenesspolynomial time algorithmrobotics

Mathematics Subject Classification ID

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

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

Cited in

(5)

• The complexity of domination problems in circle graphs
• Location, pricing and the problem of Apollonius
• scientific article; zbMATH DE number 4215407 (Why is no real title available?)
• Fast approximation algorithms for a nonconvex covering problem
• scientific article; zbMATH DE number 4059125 (Why is no real title available?)

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)