Discrete Applied Mathematics, Vol. 154, pp. 1246-1253, 2006.

I. CHARON*, S. GRAVIER**, O. HUDRY*, A. LOBSTEIN*, M. MOLLARD** & J. MONCEL**

* Centre National de la Recherche Scientifique
Ecole Nationale Supérieure des Télécommunications
46 rue Barrault, 75634 Paris cédex 13, France
{charon, hudry, lobstein}@infres.enst.fr

** Centre National de la Recherche Scientifique
Laboratoire Leibniz
46 avenue Félix Viallet, 38031 Grenoble cédex, France
{sylvain.gravier, michel.mollard, julien.moncel}@imag.fr

Abstract. Consider an oriented graph G=(V,A), a subset C of vertices, and an integer r greater than or equal to 1; for any vertex v in V, let B^-_r(v) denote the set of all vertices x such that there exists a path from x to v with at most r arcs. If for all vertices v in V, the sets B^-_r(v) $\cap$ C are all nonempty and different, then we call C an r-identifying code.
We describe a linear algorithm which gives a minimum 1-identifying code in an oriented tree.

Revenir à la page d'accueil