Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard |
| |
Authors: | Ir ne Charon, Olivier Hudry,Antoine Lobstein |
| |
Affiliation: | Département Informatique et Réseaux, Centre National de la Recherche Scientifique, URA 820, Ecole Nationale Supérieure des Télécommunications, 46 rue Barrault, 75634, Paris Cedex 13, France |
| |
Abstract: | Let G=(V,E) be an undirected graph and C a subset of vertices. If the sets Br(v)∩C, vV (respectively, vVC), are all nonempty and different, 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. |
| |
Keywords: | Complexity Coding theory Graph Identifying code Locating-dominating code NP-completeness |
本文献已被 ScienceDirect 等数据库收录! |
|