On conflict-free chromatic guarding of simple polygons

Investor logo

Warning

This publication doesn't include Institute of Computer Science. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

CAGIRICI Onur GHOSH Subir HLINĚNÝ Petr ROY Bodhayan

Year of publication 2019
Type Article in Proceedings
Conference 13th Annual International Conference on Combinatorial Optimization and Applications (COCOA'19)
MU Faculty or unit

Faculty of Informatics

Citation
Web http://dx.doi.org/10.1007/978-3-030-36412-0_49
Doi http://dx.doi.org/10.1007/978-3-030-36412-0_49
Keywords polygon visibility graph; graph coloring; polygon guarding
Description We study the problem of colouring the vertices of a polygon, such that every viewer can see a unique colour. The goal is to minimize the number of colours used. This is also known as the conflict-free chromatic guarding problem with vertex guards, and is motivated, e.g., by the problem of radio frequency assignment to sensors placed at the polygon vertices.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info