On conflict-free chromatic guarding of simple polygons

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Autoři	CAGIRICI Onur GHOSH Subir HLINĚNÝ Petr ROY Bodhayan
Rok publikování	2019
Druh	Článek ve sborníku
Konference	13th Annual International Conference on Combinatorial Optimization and Applications (COCOA'19)
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
www	http://dx.doi.org/10.1007/978-3-030-36412-0_49
Doi	https://doi.org/10.1007/978-3-030-36412-0_49
Klíčová slova	polygon visibility graph; graph coloring; polygon guarding
Popis	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.
Související projekty:	Structural properties, parameterized tractability and hardness in combinatorial problems Rozsáhlé výpočetní systémy: modely, aplikace a verifikace VIII. Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 19