Identifying codes in some subgraphs of the square lattice

被引：15
作者：
Daniel, M [1 ]
Gravier, S [1 ]
Moncel, J [1 ]
机构：
[1] UJF, CNRS, ERTe Maths a Modeler, Grp Rech GeoD,Lab Leibniz, F-38031 Grenoble, France
来源：
THEORETICAL COMPUTER SCIENCE | 2004年 / 319卷 / 1-3期
关键词：
graph theory; identifying codes; fasciagraphs;
D O I：
10.1016/j.tcs.2004.02.007
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
An identifying code of a graph is a subset of vertices C such that the sets B(v) boolean AND C are all nonempty and different. In this paper, we investigate the problem of finding identifying codes of minimum cardinality in strips and finite grids. We first give exact values for the strips of height 1 and 2, then we give general bounds for strips and finite grids. Finally, we give a sublinear algorithm which finds the minimum cardinality of an identifying code in a restricted class of graphs which includes the grid. (C) 2004 Elsevier B.V. All rights reserved.
引用
收藏
页码：411 / 421
页数：11
相关论文
共 11 条
[1]  
[Anonymous], 1979, GRAPHS NETWORKS
[2]   THE MATCHING POLYNOMIAL OF A POLYGRAPH [J].
BABIC, D ;
GRAOVAC, A ;
MOHAR, B ;
PISANSKI, T .
DISCRETE APPLIED MATHEMATICS, 1986, 15 (01) :11-24
[3]  
Charon I, 2002, ELECTRON J COMB, V9
[4]   Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard [J].
Charon, L ;
Hudry, O ;
Lobstein, A .
THEORETICAL COMPUTER SCIENCE, 2003, 290 (03) :2109-2120
[5]  
Cohen G., 1999, ELECTRON J COMB, V6, pR19
[6]  
Cohen G. D., 2001, Codes and Association Scheme. DIMACS Workshop. (Series in Discrete Mathematics and Theoretical Computer Science Vol.56), P97
[7]  
GRAVIER S, 2003, UNPUB GEN PENTOMINO
[8]   On a new class of codes for identifying vertices in graphs [J].
Karpovsky, MG ;
Chakrabarty, K ;
Levitin, LB .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1998, 44 (02) :599-611
[9]   Algebraic approach to fasciagraphs and rotagraphs [J].
Klavzar, S ;
Zerovnik, J .
DISCRETE APPLIED MATHEMATICS, 1996, 68 (1-2) :93-100
[10]  
KLAVZAR S, 2001, PREPRINT SERIES U LJ
12