Résumés
Abstract
In a graph G = (V, E), an identifying code of G (resp. a locating-dominating code of G) is a subset of vertices C ⊆ V such that N[v] ∩ C 6= ∅ for all v ∈ V , and N[u] ∩ C 6= N[v] ∩ C for all u 6= v, u, v ∈ V (resp. u, v ∈ V [integerdivide] C), where N[u] denotes the closed neighbourhood of v, that is N[u] = N(u) ∪ {u}. These codes model fault-detection problems in multiprocessor systems and are also used for designing location-detection schemes in wireless sensor networks. We give here simple reductions which improve results of the paper [I. Charon, O. Hudry, A. Lobstein, Minimizing the Size of an Identifying or Locating-Dominating Code in a Graph is NP-hard, Theoretical Computer Science 290(3) (2003), 2109–2120], and we show that minimizing the size of an identifying code or a locating-dominating code in a graph is APX-hard, even when restricted to graphs of bounded degree. Additionally, we give approximation algorithms for both problems with approximation ratio O(ln |V |) for general graphs and O(1) in the case where the degree of the graph is bounded by a constant.
Keywords:
- approximation algorithms,
- approximation hardness,
- identifying codes,
- locating-dominating codes,
- fault tolerance,
- domination problems,
- combinatorial optimization,
- graph algorithms
Veuillez télécharger l’article en PDF pour le lire.
Télécharger