𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Identifying and locating-dominating codes: NP-completeness results for directed graphs

✍ Scribed by Charon, I.; Hudry, O.; Lobstein, A.

Book ID
114636841
Publisher
IEEE
Year
2002
Tongue
English
Weight
356 KB
Volume
48
Category
Article
ISSN
0018-9448

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Minimizing the size of an identifying or
Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard
✍ IrΓ¨ne Charon; Olivier Hudry; Antoine Lobstein πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 144 KB

Let G = (V; E) be an undirected graph and C a subset of vertices. If the sets Br(v) ∩ C, v ∈ V (respectively, v ∈ V \C), are all nonempty and di erent, where Br(v) denotes the set of all points within distance r from v, we call C an r-identifying code (respectively, an r-locating-dominating code). W