Identifying and locating-dominating codes in (random) geometric networks

Kód výsledku v IS VaVaI

RIV/00216208:11320/09:00206904 - isvavai.cz

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Identifying and locating-dominating codes in (random) geometric networks

Popis výsledku v původním jazyce

We model a problem about networks built from wireless devices using identifying and locating-dominating codes in unit disk graphs. It is known that minimizing the size of an identifying code is NP-complete even for bipartite graphs. First, we improve this result by showing that the problem remains NP-complete for bipartite planar unit disk graphs. Then, we address the question of the existence of an identifying code for random unit disk graphs. Another well-studied class of codes is that of locating-dominating codes, which are less demanding than identifying codes. A locating-dominating code always exists, but minimizing its size is still NP-complete in general. We extend this result to our setting by showing that this question remains NP-complete forarbitrary planar unit disk graphs. Finally, we study the minimum size of such a code in random unit disk graphs.

Název v anglickém jazyce

Identifying and locating-dominating codes in (random) geometric networks

Popis výsledku anglicky

We model a problem about networks built from wireless devices using identifying and locating-dominating codes in unit disk graphs. It is known that minimizing the size of an identifying code is NP-complete even for bipartite graphs. First, we improve this result by showing that the problem remains NP-complete for bipartite planar unit disk graphs. Then, we address the question of the existence of an identifying code for random unit disk graphs. Another well-studied class of codes is that of locating-dominating codes, which are less demanding than identifying codes. A locating-dominating code always exists, but minimizing its size is still NP-complete in general. We extend this result to our setting by showing that this question remains NP-complete forarbitrary planar unit disk graphs. Finally, we study the minimum size of such a code in random unit disk graphs.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

1M0545: Institut Teoretické Informatiky

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2009

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 periodika

Combinatorics Probability and Computing

ISSN

0963-5483

e-ISSN

—

Svazek periodika

18

Číslo periodika v rámci svazku

6

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

28

Strana od-do

—

Kód UT WoS článku

000271683800005

EID výsledku v databázi Scopus

—