On two variations of identifying codes
From MaRDI portal
Publication:2275454
DOI10.1016/j.disc.2011.05.018zbMath1235.94077arXiv1004.4063MaRDI QIDQ2275454
Sylvain Gravier, Mickaël Montassier, Olivier Delmas, Aline Parreau
Publication date: 9 August 2011
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1004.4063
05C38: Paths and cycles
68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
94B60: Other types of codes
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68M15: Reliability, testing and fault tolerance of networks and computer systems
Cites Work
- Unnamed Item
- Unnamed Item
- On identifying codes in binary Hamming spaces
- Identifying codes of cycles with odd orders
- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- The minimum density of an identifying code in the king lattice.
- Resolvability in graphs and the metric dimension of a graph
- Identifying and locating-dominating codes on chains and cycles
- Optimal identifying codes in cycles and paths
- Identifying codes of cycles
- A linear algorithm for minimum 1-identifying codes in oriented trees
- Landmarks in graphs
- On a new class of codes for identifying vertices in graphs