Error-Correcting Codes from k-Resolving Sets

Abstract

We demonstrate a construction of error-correcting codes from graphs by means of k-resolving sets, and present a decoding algorithm which makes use of covering designs. Along the way, we determine the k-metric dimension of grid graphs (i.e., Cartesian products of paths).

Keywords

• error-correcting code
• k-resolving set
• k-metric dimension
• covering design
• uncovering
• grid graph
• 05c12
• 94b25
• 05b40
• 94b35