✦ LIBER ✦
Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard
✍ Scribed by Irène Charon; Olivier Hudry; Antoine Lobstein
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 144 KB
- Volume
- 290
- Category
- Article
- ISSN
- 0304-3975
No coin nor oath required. For personal study only.
✦ Synopsis
Let G = (V; E) be an undirected graph and C a subset of vertices. If the sets Br(v) ∩ C, v ∈ V (respectively, v ∈ V \C), are all nonempty and di erent, where Br(v) denotes the set of all points within distance r from v, we call C an r-identifying code (respectively, an r-locating-dominating code). We prove that, given a graph G and an integer k, the decision problem of the existence of an r-identifying code, or of an r-locating-dominating code, of size at most k in G, is NP-complete for any r.