On two variations of identifying codes

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

zbMATH Keywords

fault detection; cycles; identifying codes; metric basis

Mathematics Subject Classification ID

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