On conflict-free chromatic guarding of simple polygons

• 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: CAGIRICI, Onur, Subir GHOSH, Petr HLINĚNÝ a Bodhayan ROY. On conflict-free chromatic guarding of simple polygons. Online. In 13th Annual International Conference on Combinatorial Optimization and Applications (COCOA'19). Cham: Springer, Lecture Notes in Computer Science, volume 11949, 2019, s. 601-612. ISBN 978-3-030-36411-3. Dostupné z: https://dx.doi.org/10.1007/978-3-030-36412-0_49.
• www: 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
• 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