Unit Disk Visibility Graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F21%3A00125020" target="_blank" >RIV/00216224:14330/21:00125020 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-030-83823-2_61" target="_blank" >http://dx.doi.org/10.1007/978-3-030-83823-2_61</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-030-83823-2_61" target="_blank" >10.1007/978-3-030-83823-2_61</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Unit Disk Visibility Graphs

Popis výsledku v původním jazyce

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ázev v anglickém jazyce

Unit Disk Visibility Graphs

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA20-04567S" target="_blank" >GA20-04567S: Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Extended Abstracts EuroComb 2021

ISBN

9783030838225

ISSN

2297-0215

e-ISSN

—

Počet stran výsledku

7

Strana od-do

390-396

Název nakladatele

Springer International Publishing

Místo vydání

Cham

Místo konání akce

Cham

Datum konání akce

1. 1. 2021

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—