On conflict-free chromatic guarding of simple polygons

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.

Základní údaje

Originální název

On conflict-free chromatic guarding of simple polygons

Autoři

CAGIRICI, Onur (792 Turecko, domácí), Subir GHOSH (356 Indie), Petr HLINĚNÝ (203 Česká republika, garant, domácí) a Bodhayan ROY (356 Indie)

Vydání

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

Nakladatel

Springer, Lecture Notes in Computer Science, volume 11949

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

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

Forma vydání

elektronická verze "online"

Odkazy

URL

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/19:00107778

Organizační jednotka

Fakulta informatiky

ISBN

978-3-030-36411-3

ISSN

DOI

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

Klíčová slova anglicky

polygon visibility graph; graph coloring; polygon guarding

Štítky

core_B, firank_B, formela-conference

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

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.

---

Návaznosti

GA17-00837S, projekt VaV	Název: Strukturální vlastnosti, parametrizovaná řešitelnost a těžkost v kombinatorických problémech Investor: Grantová agentura ČR, Structural properties, parameterized tractability and hardness in combinatorial problems
MUNI/A/1018/2018, interní kód MU	Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace VIII. Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace VIII., DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
MUNI/A/1040/2018, interní kód MU	Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 19 (Akronym: SKOMU) Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 19, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty