Vertex-to-point conflict-free chromatic guarding is NP-hard

DOI10.1007/978-3-030-96731-4_10MaRDI QIDQ2154089zbMATH OpenOpenAlexFDO

Authors C. Iwamoto, Tatsuaki Ibusuki

Publication date 13 July 2022

Full work available at URL https://doi.org/10.1007/978-3-030-96731-4_10

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A combinatorial theorem in plane geometry
• Computational complexity of art gallery problems
• Computational complexity of the chromatic art gallery problem for orthogonal polygons
• Conflict-free chromatic art gallery coverage
• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 177851 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Inapproximability results for guarding polygons and terrains
• On conflict-free chromatic guarding of simple polygons
• On guarding the vertices of rectilinear domains
• Planar 3-SAT with a clause/variable cycle
• Tight bounds for conflict-free chromatic guarding of orthogonal art galleries
• Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons

This page was built for publication: Vertex-to-point conflict-free chromatic guarding is NP-hard

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