Identifying and Locating–Dominating Codes in (Random) Geometric Networks
From MaRDI portal
Publication:3557518
DOI10.1017/S0963548309990344zbMath1187.94040MaRDI QIDQ3557518
Jean-Sébastien Sereni, Tobias Müller
Publication date: 23 April 2010
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Related Items
Identification of points using disks, The identifying code, the locating-dominating, the open locating-dominating and the locating total-dominating problems under some graph operations, Tolerant identification with Euclidean balls, Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity, Linear-time algorithms for three domination-based separation problems in block graphs, Complexity and approximation for discriminating and identifying code problems in geometric setups, The binary locating-dominating number of some convex polytopes, Locating and identifying codes in circulant networks, Parameterized and approximation complexity of \textsc{Partial VC Dimension}, Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds., Locating and identifying codes in circulant graphs, Discriminating Codes in Geometric Setups, Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes, Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs, Polyhedra associated with locating-dominating, open locating-dominating and locating total-dominating sets in graphs, On the limiting distribution of the metric dimension for random forests
Cites Work
- Codes identifying sets of vertices in random networks
- Unit disk graphs
- Unit disk graph recognition is NP-hard
- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- On robust and dynamic identifying codes
- Planar Formulae and Their Uses
- A correlation inequality and a poisson limit theorem for nonoverlapping balanced subgraphs of a random graph
- On a new class of codes for identifying vertices in graphs
- Random Geometric Graphs