|
|||||
|
|
A linear algorithm for minimum 1-identifying codes in oriented trees |
|
| Authors: | Irène Charon |
| Institution: | a GET, Télécom Paris & CNRS, LTCI UMR 5141, 46 rue Barrault 75634, Paris Cedex 13, France b CNRS, Laboratoire Leibniz, 46 avenue Félix Viallet 38031, Grenoble Cedex, France c CNRS, LTCI UMR 5141 & GET, Télécom Paris, 46 rue Barrault 75634, Paris Cedex 13, France |
| Abstract: | Consider an oriented graph G=(V,A), a subset of vertices C⊆V, and an integer r?1; for any vertex v∈V, let  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∈V, the sets  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 any oriented tree. |
| Keywords: | Graph Oriented graph Linear algorithm Tree Identifying code |
| 本文献已被 ScienceDirect 等数据库收录！ | |