On conflict-free chromatic guarding of simple polygons

CAGIRICI, Onur, Subir GHOSH, Petr HLINĚNÝ and 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, p. 601-612. ISBN 978-3-030-36411-3. Available from: https://dx.doi.org/10.1007/978-3-030-36412-0_49.

Basic information

Original name

On conflict-free chromatic guarding of simple polygons

Authors

CAGIRICI, Onur (792 Turkey, belonging to the institution), Subir GHOSH (356 India), Petr HLINĚNÝ (203 Czech Republic, guarantor, belonging to the institution) and Bodhayan ROY (356 India)

Edition

Cham, 13th Annual International Conference on Combinatorial Optimization and Applications (COCOA'19), p. 601-612, 12 pp. 2019

Publisher

Springer, Lecture Notes in Computer Science, volume 11949

---

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

electronic version available online

References:

URL

Impact factor

Impact factor: 0.402 in 2005

RIV identification code

RIV/00216224:14330/19:00107778

Organization unit

Faculty of Informatics

ISBN

978-3-030-36411-3

ISSN

DOI

http://dx.doi.org/10.1007/978-3-030-36412-0_49

Keywords in English

polygon visibility graph; graph coloring; polygon guarding

Tags

core_B, firank_B, formela-conference

Tags

International impact, Reviewed

---

Abstract

V originále

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.

---

Links

GA17-00837S, research and development project	Name: Strukturální vlastnosti, parametrizovaná řešitelnost a těžkost v kombinatorických problémech Investor: Czech Science Foundation
MUNI/A/1018/2018, interní kód MU	Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace VIII. Investor: Masaryk University, Category A
MUNI/A/1040/2018, interní kód MU	Name: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 19 (Acronym: SKOMU) Investor: Masaryk University, Category A