On identifying codes in the King grid that are robust against edge deletions (Q1010708): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q1261013 |
Set profile property. |
||
(One intermediate revision by one other user not shown) | |||
Property / author | |||
Property / author: Iiro S. Honkala / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Latest revision as of 02:53, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On identifying codes in the King grid that are robust against edge deletions |
scientific article |
Statements
On identifying codes in the King grid that are robust against edge deletions (English)
0 references
7 April 2009
0 references
Summary: Assume that \(G = (V, E)\) is an undirected graph, and \(C \subseteq V\). For every \(v \in V\), we denote \(I_r(G;v) = \{ u \in C: d(u,v) \leq r\}\), where \(d(u,v)\) denotes the number of edges on any shortest path from \(u\) to \(v\). If all the sets \(I_r(G;v)\) for \(v \in V\) are pairwise different, and none of them is the empty set, the code \(C\) is called \(r\)-identifying. If \(C\) is \(r\)-identifying in all graphs \(G'\) that can be obtained from \(G\) by deleting at most \(t\) edges, we say that \(C\) is robust against \(t\) known edge deletions. Codes that are robust against \(t\) unknown edge deletions form a related class. We study these two classes of codes in the king grid with the vertex set \({\mathbb Z}^2\) where two different vertices are adjacent if their Euclidean distance is at most \(\sqrt{2}\).
0 references
identifying code
0 references
edge deletion
0 references
king grid
0 references
optimal code
0 references
code robust against edge deletion
0 references