AGAOGLU, Deniz a Onur CAGIRICI. Unit Disk Visibility Graphs. In Nešetřil, Jaroslav and Perarnau, Guillem and Rué, Juanjo and Serra, Oriol. Extended Abstracts EuroComb 2021. Cham: Springer International Publishing, 2021. s. 390--396. ISBN 978-3-030-83823-2. doi:10.1007/978-3-030-83823-2_61.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název Unit Disk Visibility Graphs
Autoři AGAOGLU, Deniz a Onur CAGIRICI.
Vydání Cham, Extended Abstracts EuroComb 2021, od s. 390--396, 7 s. 2021.
Nakladatel Springer International Publishing
Další údaje
Originální jazyk angličtina
Typ výsledku Stať ve sborníku
Obor 10201 Computer sciences, information science, bioinformatics
Stát vydavatele Švýcarsko
Utajení není předmětem státního či obchodního tajemství
Forma vydání elektronická verze "online"
Organizační jednotka Fakulta informatiky
ISBN 978-3-030-83823-2
Doi http://dx.doi.org/10.1007/978-3-030-83823-2_61
Klíčová slova anglicky unit disk graphs; visibility graphs; 3-coloring problem; NP-hardness
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnila: RNDr. Deniz Agaoglu Cagirici, učo 459192. Změněno: 23. 10. 2021 17:54.
Anotace
We study unit disk visibility graphs, where the visibility relation between a pair of geometric entities is defined by not only obstacles, but also the distance between them. This particular graph class models real world scenarios more accurately compared to the conventional visibility graphs. We first define and classify the unit disk visibility graphs, and then show that the 3-coloring problem is NP-complete when unit disk visibility model is used for a set of line segments (which applies to a set of points) and for a polygon with holes.
Návaznosti
GA20-04567S, projekt VaVNázev: Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech
Investor: Grantová agentura ČR, Standardní projekty
MUNI/A/1108/2020, interní kód MUNázev: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace X. (Akronym: SV-FI MAV X.)
Investor: Masarykova univerzita, Specifický výzkum - podpora studentských projektů
MUNI/A/1549/2020, interní kód MUNázev: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 21 (Akronym: SKOMU)
Investor: Masarykova univerzita, Specifický výzkum - podpora studentských projektů
VytisknoutZobrazeno: 22. 1. 2022 04:42