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 (16)
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
This page was built for publication: Identifying and Locating–Dominating Codes in (Random) Geometric Networks
