Geodesic
Error-Correcting Codes from k -Resolving Sets
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 2, pp. 341-355.

Voir la notice de l'article provenant de la source Library of Science

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 
@article{DMGT_2019_39_2_a3,
     author = {Bailey, Robert F. and Yero, Ismael G.},
     title = {Error-Correcting {Codes} from k {-Resolving} {Sets}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {341--355},
     publisher = {mathdoc},
     volume = {39},
     number = {2},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a3/}
}
TY  - JOUR
AU  - Bailey, Robert F.
AU  - Yero, Ismael G.
TI  - Error-Correcting Codes from k -Resolving Sets
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 341
EP  - 355
VL  - 39
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a3/
LA  - en
ID  - DMGT_2019_39_2_a3
ER  - 
%0 Journal Article
%A Bailey, Robert F.
%A Yero, Ismael G.
%T Error-Correcting Codes from k -Resolving Sets
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 341-355
%V 39
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a3/
%G en
%F DMGT_2019_39_2_a3
Bailey, Robert F.; Yero, Ismael G. Error-Correcting Codes from k -Resolving Sets. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 2, pp. 341-355. http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a3/

[1] R.F. Bailey, Uncoverings-by-bases for base-transitive permutation groups, Des. Codes Cryptogr. 41 (2006) 153–176. doi:10.1007/s10623-006-9005-x

[2] R.F. Bailey, Error-correcting codes from permutation groups, Discrete Math. 309 (2009) 4253–4265. doi:10.1016/j.disc.2008.12.027

[3] R.F. Bailey and P.J. Cameron, Base size, metric dimension and other invariants of groups and graphs, Bull. Lond. Math. Soc. 43 (2011) 209–242. doi:10.1112/blms/bdq096

[4] R.F. Bailey and B. Stevens, Uncoverings on graphs and network reliability, Australas. J. Combin. 50 (2011) 219–231.

[5] A.F. Beardon and J.A. Rodríguez-Velázquez, On the k-metric dimension of metric spaces, preprint. arXiv:1603.04049.

[6] L.M. Blumenthal, Theory and Applications of Distance Geometry (Clarendon Press, Oxford, 1953).

[7] P.J. Cameron, Permutation codes, European J. Combin. 31 (2010) 482–490. doi: 10.1016/j.ejc.2009.03.044

[8] G. Chartrand, L. Eroh, M.A. Johnson and O.R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000) 99–113. doi:10.1016/S0166-218X(00)00198-0

[9] W. Chu, C.J. Colbourn and P. Dukes, Constructions for permutation codes in powerline communications, Des. Codes Cryptogr. 32 (2004) 51–64. doi:10.1023/B:DESI.0000029212.52214.71

[10] C.J. Colbourn and J.H. Dinitz (Editors), Handbook of Combinatorial Designs (Second Edition) (CRC Press, Boca Raton, 2007).

[11] T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms (Second Edition) (MIT Press, Cambridge/McGraw-Hill, Boston, 2001).

[12] A. Estrada-Moreno, J.A. Rodríguez-Velázquez and I.G. Yero, The k-metric dimension of a graph, Appl. Math. Inf. Sci. 9 (2015) 2829–2840.

[13] A. Estrada-Moreno, I.G. Yero and J.A. Rodríguez-Velázquez, The k-metric dimension of corona product graphs, Bull. Malays. Math. Sci. Soc. 39 (2016) 135–156. doi:10.1007/s40840-015-0282-2

[14] A. Estrada-Moreno, I.G. Yero and J.A. Rodríguez-Velázquez, The k-metric dimension of the lexicographic product of graphs, Discrete Math. 339 (2016) 1924–1934. doi:10.1016/j.disc.2015.12.024

[15] D.M. Gordon, La Jolla Covering Repository. www.ccrwest.org/cover.html

[16] F. Harary and R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191–195.

[17] S. Khuller, B. Raghavachari and A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70 (1996) 217–229. doi:10.1016/0166-218X(95)00106-2

[18] H.-J. Kroll and R. Vincenti, Antiblocking systems and PD-sets, Discrete Math. 308 (2008) 401–407. doi:10.1016/j.disc.2006.11.056

[19] W. H. Mills and R.C. Mullin, Coverings and packings, in: Contemporary Design Theory: A collection of surveys, J.H. Dinitz and D.R. Stinson (Ed(s)), (John Wiley & Sons, New York, 1992) 371–399.

[20] V. Pless, Introduction to the Theory of Error-Correcting Codes (Third Edition) (John Wiley & Sons, New York, 1998). doi:10.1002/9781118032749

[21] J. Schönheim, On coverings, Pacific J. Math. 14 (1964) 1405–1411. doi:10.2140/pjm.1964.14.1405

[22] A. Sebő and E. Tannier, On metric generators of graphs, Math. Oper. Res. 29 (2004) 383–393. doi:10.1287/moor.1030.0070

[23] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549–559.

[24] I. Tamo and M. Schwartz, Correcting limited-magnitude errors in the rank-modulation scheme, IEEE Trans. Inform. Theory 56 (2010) 2551–2560. doi:10.1109/TIT.2010.2046241

[25] I.G. Yero, A. Estrada-Moreno and J.A. Rodríguez-Velázquez, Computing the kmetric dimension of graphs, Appl. Math. Comput. 300 (2017) 60–69. doi:10.1016/j.amc.2016.12.005