D 2021

Unit Disk Visibility Graphs

AGAOGLU, Deniz a Onur CAGIRICI

Základní údaje

Originální název

Unit Disk Visibility Graphs

Autoři

AGAOGLU, Deniz (792 Turecko, domácí) a Onur CAGIRICI (792 Turecko, domácí)

Vydání

Cham, Extended Abstracts EuroComb 2021, od s. 390-396, 7 s. 2021

Nakladatel

Springer International Publishing

Další údaje

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"

Kód RIV

RIV/00216224:14330/21:00125020

Organizační jednotka

Fakulta informatiky

ISBN

978-3-030-83822-5

ISSN

DOI

Klíčová slova anglicky

unit disk graphs; visibility graphs; 3-coloring problem; NP-hardness

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 6. 4. 2023 11:02, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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 VaV
Název: Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech
Investor: Grantová agentura ČR, Structure of tractable instances of hard algorithmic problems on graphs
MUNI/A/1108/2020, interní kód MU
Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace X. (Akronym: SV-FI MAV X.)
Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace X.
MUNI/A/1145/2021, interní kód MU
Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace XI. (Akronym: SV-FI MAV XI.)
Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace XI.
MUNI/A/1549/2020, interní kód MU
Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 21 (Akronym: SKOMU)
Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 21