Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard

被引：106

作者：

Charon, L ^{[1
]}

Hudry, O ^{[1
]}

Lobstein, A ^{[1
]}

机构：

[1] Ecole Natl Super Telecommun Bretagne, CNRS, Dept Informat & Reseaux, URA 820, F-75634 Paris 13, France

来源：

THEORETICAL COMPUTER SCIENCE | 2003年 / 290卷 / 03期

关键词：

complexity; coding theory; graph; identifying code; locating-dominating code; NP-completeness;

D O I：

10.1016/S0304-3975(02)00536-4

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Let G = (V, E) be an undirected graph and C a subset of vertices. If the sets B-r(v) boolean AND C, v is an element of V (respectively, v is an element of V \ C), are all nonempty and different, where B-r(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. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：2109 / 2120

页数：12