On the Identification of Sets of Points in the Square Lattice

   Abstract. Identifying codes in the square lattice are considered. The motivation for these codes is the following: if a multiprocessor system is modelled by the square lattice, then we can locate faulty processors in the system with the aid of identifying codes. Constructions, some of which are optimal, are given.     

On the Identification of Sets of Points in the Square Lattice

Abstract. Identifying codes in the square lattice are considered. The motivation for these codes is the following: if a multiprocessor system is modelled by the square lattice, then we can locate faulty processors in the system with the aid of identifying codes. Constructions, some of which are optimal, are given.     

On Codes Identifying Sets of Vertices in Hamming Spaces

A code is called (t, 2)-identifying if for all the words x, y(x y) and the sets (B _t (x) B _t (y)) C and are nonempty and different. Constructions of such codes and a lower bound on the cardinality of these codes are given. The lower bound is shown to be sharp in some cases. We also discuss a more general notion of -identifying codes and introduce weakly identifying codes.     

Optimal t-Edge-Robust r-Identifying Codes in the King Lattice

Locating faulty processors in a multiprocessor system gives a motivation for identifying codes. The concept of a t-edge-robust r-identifying code was introduced in [8]. We consider these codes in the king lattice and give several optimal densities. Research supported by the Academy of Finland under grants 207303 and 111940.     

Improved lower bound for locating-dominating codes in binary Hamming spaces

Designs, Codes and Cryptography - In this article, we study locating-dominating codes in binary Hamming spaces $$\mathbb {F}^n$$ . Locating-dominating codes have been widely studied since their...     

Locating–dominating codes in paths

Bertrand, Charon, Hudry and Lobstein studied, in their paper in 2004 [1], r-locating–dominating codes in paths P_n. They conjectured that if r≥2 is a fixed integer, then the smallest cardinality of an r-locating–dominating code in P_n, denoted by , satisfies for infinitely many values of n. We prove that this conjecture holds. In fact, we show a stronger result saying that for any r≥3 we have for all n≥n_r when n_r is large enough. In addition, we solve a conjecture on location–domination with segments of even length in the infinite path.     

On robust identification in the square and king grids

Fault diagnosis of multiprocessor systems gives the motivation for robust identifying codes. We provide robust identifying codes for the square and king grids. Often we are able to find optimal such codes.     

Optimal Identifying Codes in Cycles and Paths

The concept of identifying codes in a graph was introduced by Karpovsky et?al. (in IEEE Trans Inf Theory 44(2):599–611, 1998). These codes have been studied in several types of graphs such as hypercubes, trees, the square grid, the triangular grid, cycles and paths. In this paper, we determine the optimal cardinalities of identifying codes in cycles and paths in the remaining open cases.