Abstract
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 for arbitrary planar unit disk graphs. Finally, we study the minimum size of such a code in random unit disk graphs.