COMPUTER SCIENCE COLLOQUIUM

Identifying Codes in Grids

Frederic Havet CNRS, Inria, I3S, Inria Sophia Antipolis, Project-team COATI Université Côte d’Azur

Tuesday, 10 April, 2018 at 14:15 IMADA's Seminar Room

ABSTRACT

Let $G$ be a graph and v a vertex of $G$. The closed neighbourhood of $v$, denoted by $N[v]$, is the set of vertices adjacent or equal to $v$ in $G$. Given a set $C$ of vertices, the identifier of a vertex $v$ is the intersection of $N[v]$ and $C$. We say that $C$ is an identifying code of $G$ if every vertex has non-empty identifier and, for all distinct $u$ and $v$, $u$ and $v$ have distinct identifiers.

The problem of finding low-density identifying codes was introduced by Karpovsky et al. in relation to fault diagnosis in arrays of processors. Here the vertices of an identifying code correspond to controlling processors able to check themselves and their neighbours. Thus the identifying property guarantees location of a faulty processor from the set of "complaining" controllers. Particular interest was dedicated to grids as many processor networks have a grid topology.

In this talk, we present new results on low-density codes in three common kind of infinite grids, namely square grids, triangular grids, and king grids.

This talk is based on one article with M. Bouznif, M. Preissman, and two with R. Dantas and R. Sampaio.

Host: Jørgen Bang-Jensen

---

SDU HOME | IMADA HOME | Previous Page

---

Daniel Merkle