Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Identification in Z^2 Using Eu...

Identification in Z^2 Using Euclidean Balls

Ville Junnila, Tero Laihonen, Identification in Z^2 Using Euclidean Balls. Discrete Applied Mathematics 159, 335–343, 2011.

Abstract:

The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin. These codes find their application, for example, in sensor networks. The network is modelled by a graph. In this paper, the goal is to find good identifying codes in a natural setting, that is, in a graph $\mathcal{E}_r=(V,E)$ where $V=\Z^2$ is the set of vertices and each vertex (sensor) can check its neighbours within Euclidean distance $r$. We also consider a graph closely connected to a well-studied king grid, which provides optimal identifying codes for $\mathcal{E}_{\sqrt{5}}$ and
$\mathcal{E}_{\sqrt{13}}$.

BibTeX entry:

@ARTICLE{jJuLa11a,
  title = {Identification in Z^2 Using Euclidean Balls},
  author = {Junnila, Ville and Laihonen, Tero},
  journal = {Discrete Applied Mathematics},
  volume = {159},
  pages = {335–343},
  year = {2011},
  keywords = {Identifying code; optimal code; Euclidean distance; sensor network; fault diagnosis},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 2

Edit publication