On Iiro Honkala's contributions to identifying codes

• Autorzy: Hudry Olivier , Junnila Ville , Lobstein Antoine

Identyfikatory

DOI

10.3233/FI-242178

• Języki publikacji: EN

Abstrakty

EN

A set C of vertices in a graph G = (V, E) is an identifying code if it is dominating and any two vertices of V are dominated by distinct sets of codewords. This paper presents a survey of Iiro Honkala’s contributions to the study of identifying codes with respect to several aspects: complexity of computing an identifying code, combinatorics in binary Hamming spaces, infinite grids, relationships between identifying codes and usual parameters in graphs, structural properties of graphs admitting identifying codes, and number of optimal identifying codes.

Słowa kluczowe

EN

graph theory; combinatorics; identifying codes; domination; separation; twin-free graphs; complexity; binary Hamming spaces; infinite grids; classic parameters of graphs; number of optimal solutions

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2024
• Tom: Vol. 191, nr 3-4
• Strony: 165--196
• Opis fizyczny: Bibliogr. 85 poz., rys.

Twórcy

autor

Hudry Olivier

• Télélcom Paris, France

autor

Junnila Ville

• University of Turku, Finland

autor

Lobstein Antoine

• CNRS, Universit´e Paris-Saclay, France

Bibliografia

• [1] Auger D. Induced paths in twin-free graphs, Electron. J. Combin. 15(1) (2008), N17. doi:10.37236/892.
• [2]* Auger D, Charon I, Honkala I, Hudry O, and Lobstein A. Edge number, minimum degree, maximum independent set, radius and diameter in twin-free graphs, Adv. Math. Commun. 3(1) (2009), 97-114. Erratum 2009. 3(4):429-430. doi:10.3934/amc.2009.3.97.
• [3] Auger D, Charon I, Hudry O, and Lobstein A. Complexity results for identifying codes in planar graphs, Int. Trans. Oper. Res. 2010. 17(6):691-710. doi:10.1111/j.1475-3995.2009.00750.x.
• [4] Ben-Haim Y, and Litsyn S. Exact minimum density of codes identifying vertices in the square grid, SIAM J. Discrete Math. 2005. 19:69-82. doi:10.1137/S089548010444408.
• [5] Bertrand N. Codes identifiants et codes localisateurs-dominateurs sur certains graphes, mémoire de stage de maîtres, ENST, Paris, France 2001, 28 pages.
• [6]* Blass U, Honkala I, and Litsyn S. On the size of identifying codes, Lecture Notes in Comput. Sci. 1999. 1719:142-147. doi:10.1007/3-540-46796-3 14.
• [7]* Blass U, Honkala I, and Litsyn S. On binary codes for identification, J. Combin. Des. 8 (2000), 151-156. https://doi.org/10.1002/(SICI)1520-6610(2000)8:2<151.
• [8]* Blass U, Honkala I, and Litsyn S. Bounds on identifying codes, Discrete Math., Selected Papers in Honor of Helge Tverberg, 2001. 241:119-128.
• [9] Charon I, Cohen G, Hudry O, and Lobstein A. New identifying codes in the binary Hamming space, European J. Combin. 2010. 31:491-501. doi:10.1016/j.ejc.2009.03.032.
• [10]* Charon I, Honkala I, Hudry O and Lobstein A. General bounds for identifying codes in some infinite regular graphs, Electron. J. Combin. 2001. 8(1):R39.
• [11]* Charon I, Honkala I, Hudry O, and Lobstein A. The minimum density of an identifying code in the king lattice, Discrete Math. 2004. 276:95-109. doi:10.1016/S0012-365X(03)00306-6.
• [12]* Charon I, Honkala I, Hudry O and Lobstein A, Structural properties of twin-free graphs, Electron. J. Combin. 2007. 14(1):R16.
• [13]* Charon I, Honkala I, Hudry O and Lobstein A, Minimum sizes of identifying codes in graphs differing by one vertex, Cryptogr. Commun. 2013. 5:119-136.
• [14]* Charon I, Honkala I, Hudry O and Lobstein A. Minimum sizes of identifying codes in graphs differing by one edge, Cryptogr. Commun. 2014. 6:157-170. doi:10.1007/s12095-013-0094-x.
• [15] Charon I, Hudry O, and Lobstein A. Identifying codes with small radius in some infinite regular graphs, Electron. J. Combin. 2002. 9(1): R11.
• [16] Charon I, Hudry O, and Lobstein A. Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard, Theoret. Comput. Sci. 2003. 290:2109-2120. doi:10.1016/S0304-3975(02)00536-4.
• [17] Charon I, Hudry O, and Lobstein A. Extremal cardinalities for identifying and locating-dominating codes, Discrete Math. 2007. 307:356-366. doi:10.1016/j.disc.2005.09.027.
• [18]* Cohen G, Gravier S, Honkala I, Lobstein A, Mollard M, Payan Ch, and Zémor G. Improved identifying codes for the grid, Electron. J. Combin. 1999. 6(1):R19.
• [19]* Cohen G, Honkala I, Litsyn S, and Lobstein A. Covering Codes, North-Holland Publishing Co. (1997).
• [20]* Cohen G, Honkala I, Lobstein A, and Zémor G. Bounds for codes identifying vertices in the hexagonal grid, SIAM J. Discrete Math. 2000. 13:492-504. doi:10.1137/S0895480199360990.
• [21]* Cohen G, Honkala I, Lobstein A, and Zémor G. On identifying codes, in A. Barg and S. Litsyn (eds), Proceedings of DIMACS Workshop on Codes and Association Schemes ’99, Piscataway, USA, American Mathematical Society. 2001. 56:97-109.
• [22]* Cohen G, Honkala I, Lobstein A, and Z´emor G. On codes identifying vertices in the two-dimensional square lattice with diagonals, IEEE Trans. Comput. 2001. 50:174-176. doi:10.1109/12.908992.
• [23] Cukierman A, and Yu G. New bounds on the minimum density of an identifying code for the infinite hexagonal grid, Discrete Appl. Math. 2013. 161:2910-2924. doi:10.1016/j.dam.2013.06.002.
• [24] Daniel M. Codes identifiants, mémoire de DEA ROCO. Université Joseph Fourier, Grenoble, France. 2003, 46 pages.
• [25] Dhanalakshmi R, and Durairajan C. Constructions of r-identifying codes and (r, ≤ l)-identifying codes, Indian J. Pure Appl. Math. 2019. 50:531-547. doi:10.1007/s13226-019-0343-6.
• [26] Exoo G, Junnila V, and Laihonen T. On location-domination of set of vertices in cycles and paths, Congr. Numer. 2010. 202:97-112.
• [27] Exoo G, Junnila V, and Laihonen T, and Ranto S. Locating vertices using codes, Congr. Numer. 2008. 191:143-159.
• [28] Exoo G, Junnila V, and Laihonen T, and Ranto S. Upper bounds for binary identifying codes, Adv. in Appl. Math. 2009. 42:277-289. doi:10.1016/j.aam.2008.06.004.
• [29] Exoo G, Junnila V, and Laihonen T, and Ranto R. Improved bounds on identifying codes in binary Hamming spaces, European J. Combin. 2010. 31:813-827. doi:10.1016/j.ejc.2009.09.002.
• [30] Exoo G, Laihonen T, and Ranto S. Improved upper bounds on binary identifying codes, IEEE Trans. Inform. Theory. 2007. 53:4255-4260. doi:10.1109/TIT.2007.907434.
• [31] Exoo G, Laihonen T, and Ranto S. New bounds on binary identifying codes, Discrete Appl. Math. 2008. 156:2250-2263. doi:10.1016/j.dam.2007.09.017.
• [32] Foucaud F. Algorithmic and combinatorial aspects of identifying codes in graphs, PhD thesis, Université Bordeaux 1, France 2012.
• [33] Foucaud F. Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes. J. Discrete Alg. 2015. 31:48-68. doi:10.1016/j.jda.2014.08.004.
• [34] Foucaud F, Guerrini E, Kovˇse M, Naserasr R, Parreau A, and Valicov P. Extremal graphs for the identifying
• code problem, European J. Combin. 2011. 32:628-638. doi:10.1016/j.ejc.2011.01.002.
• [35] Foucaud F, and Kovše M. Identifying path covers in graphs, J. Discrete Alg. 2013. 23:21-34. doi:10.1016/j.jda.2013.07.006.
• [36] Foucaud F, Laihonen T, and Parreau A. An improved lower bound for (1, 6 2)-identifying codes in the king grid, Adv. Math. Commun. 2014. 8:35-52. doi:10.3934/amc.2014.8.35.
• [37] Gravier S, and Moncel J. Construction of codes identifying sets of vertices, Electron. J. Combin. 2005. 12(1):R13. doi:10.37236/1910.
• [38] Gravier S, and Moncel J. On graphs having a V \ {x} set as an identifying code, Discrete Math. 2007. 307:432-434. doi:10.1016/j.disc.2005.09.035.
• [39]* Honkala I. On the identifying radius of codes, Proceedings of the Seventh Nordic Combinatorial Conference, Turku, TUCS Gen. Publ. 1999. 15:39-43.
• [40]* Honkala I. An optimal strongly identifying code in the infinite triangular grid, Electron. J. Combin. 2010. 17(1):R91. doi:10.37236/363.
• [41]* Honkala I, Hudry O, and Lobstein A. On the number of optimal identifying codes in a twin-free graph, Discrete Appl. Math. 2015. 180:111-119. doi:10.1016/j.dam.2014.08.020.
• [42]* Honkala I, Hudry O, and Lobstein A. On the ensemble of optimal identifying codes in a twin-free graph, Cryptogr. Commun. 2016. 8:139-153. doi:10.1007/s12095-015-0148-3.
• [43]* Honkala I, Karpovsky MG, and Levitin LB. On robust and dynamic identifying codes, IEEE Trans. Inform. Theory 2006. 52: 599-612. doi:10.1109/TIT.2005.862097.
• [44]* Honkala I, and Laihonen T. On identifying codes in the triangular and square grids, SIAM J. Comput. 2004. 33:304-312. doi:10.1137/S009753970343311.
• [45]* Honkala I, and Laihonen T. On identifying codes that are robust against edge changes, Inform. and Comput. 2007. 205:1078-1095. doi:10.1016/j.ic.2007.01.003.
• [46]* Honkala I, and Laihonen T. On a new class of identifying codes in graphs, Inform. Process. Lett. 2007. 102:92-98. doi:10.1016/j.ipl.2006.11.007.
• [47]* Honkala I, and Laihonen T. On vertex-robust identifying codes of level three, Ars Combin. 2010. 94:115-127.
• [48]* Honkala I, Laihonen T, and Ranto S. On codes identifying sets of vertices in Hamming spaces, Des. Codes Cryptogr. 2001. 24:193-204. doi:10.1023/A:1011256721935.
• [49]* Honkala I, Laihonen T, and Ranto S. On strongly identifying codes, Discrete Math. 2002. 254:191-205. doi:10.1016/S0012-365X(01)00357-0.
• [50]* Honkala I, Laihonen T, and Ranto S. On locating-dominating codes in binary Hamming spaces, Discrete Math. Theor. Comput. Sci. 2004. 6:265-282. doi:10.46298/dmtcs.322.
• [51]* Honkala I, and Lobstein A. On the density of identifying codes in the square lattice, J. Combin. Theory, Ser. B 2002. 85:297-306. doi:10.1006/jctb.2001.2106.
• [52]* Honkala I, and Lobstein A. On identifying codes in binary Hamming spaces, J. Combin. Theory, Ser. A 2002.99:232-243. doi:10.1006/jcta.2002.3263.
• [53]* Honkala I, and Lobstein A, On the complexity of the identification problem in Hamming spaces, Acta Inform. 2002. 38:839-845. doi:10.1007/s00236-002-0093-4.
• [54]* Honkala I, and Lobstein A. On identification in Z2 using translates of given patterns, J. UCS 2003. 9(10):1204-1219. doi:10.3217/jucs-009-10-1204.
• [55] Hudry O, and Lobstein A. More results on the complexity of identifying problems in graphs, Theor. Comput. Sci. 2016. 626:1-12. doi:10.1016/j.tcs.2016.01.021.
• [56] Hudry O, and Lobstein A. Unique (optimal) solutions: complexity results for identifying and locating-dominating codes, Theor. Comput. Sci. 2019. 767:83-102. doi:10.1016/j.tcs.2018.09.034.
• [57] Janson S, and Laihonen T. On the size of identifying codes in binary hypercubes, J. Combin. Theory, Ser. A 2009. 116:1087-1096. doi:10.1016/j.jcta.2009.02.004.
• [58] Jean D. Watching systems, identifying, locating-dominating and discriminating codes in graphs, https://dragazo.github.io/bibdom/main.pdf
• [59] Junnila V. New lower bound for 2-identifying code in the square grid, Discrete Appl. Math. 2013. 161:2042-2051. doi:10.1016/j.dam.2013.02.032.
• [60] Junnila V, and Laihonen T. Identification in Z2 using Euclidean balls, Discrete Appl. Math. 2011. 159:335-343. doi:10.1016/j.dam.2010.12.008.
• [61] Junnila V, and Laihonen T. Optimal lower bound for 2-identifying codes in the hexagonal grid, Electron. J. Combin. 2012. 19(2):P38. doi:10.37236/2414.
• [62] Karpovsky MG, Chakrabarty K, and Levitin LB. On a new class of codes for identifying vertices in graphs, IEEE Trans. Inform. Theory 1998. 44:599-611.
• [63] Laihonen T. Sequences of optimal identifying codes, IEEE Trans. Inform. Theory 2002. 48:774-776. doi:10.1109/18.986043.
• [64] Laihonen T. Optimal codes for strong identification, European J. Combin. 2002. 23:307-313. doi:10.1006/eujc.2002.0571.
• [65] Laihonen T. On optimal edge-robust and vertex-robust (1, ≤ ℓ)-identifying codes, SIAM J. Discrete Math. 2005. 18(4):825-834. doi:10.1137/S0895480104440754.
• [66] Laihonen T. Optimal t-edge-robust r-identifying codes in the king lattice, Graphs Combin. 2006. 22:487-496. doi:10.1007/s00373-006-0682-z.
• [67] Laihonen T. On edge-robust (1, ≤ ℓ)-identifying codes in binary Hamming spaces, Int. J. Pure Appl. Math. 2007. 36:87-102. doi:10.48550/arXiv.cs/0703066.
• [68] Laihonen T, and Ranto S. Codes identifying sets of vertices, in Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (Melbourne, 2001), Lecture Notes in Comput. Sci. 2001. (2227):82-91. doi:10.1007/3-540-45624-4 9.
• [69] Laihonen T, and Ranto S. Families of optimal codes for strong identification, Discrete Appl. Math. 2002. 121(1-3):203-213. doi:10.1016/S0166-218X(01)00248-7.
• [70] Lobstein A, Hudry O, and Charon I. Locating-domination and identification, in T. Hayes, S. Hedetniemi, M. Henning (eds), Topics in Domination in Graphs, Springer 2020. pp. 251-299. https://hal.science/hal-02916929.
• [71] Martin R, and Stanton B. Lower bounds for identifying codes in some infinite grids, Electron. J. Combin. 2010. 17(1):R122. doi:10.48550/arXiv.1004.3281.
• [72] Moncel J. Monotonicity of the minimum cardinality of an identifying code in the hypercube, Discrete Appl. Math. 2006. 154:898-899. doi:10.1016/j.dam.2005.05.030.
• [73] Pelto M. New bounds for (r, 6 2)-identifying codes in the infinite king grid, Cryptogr. Commun. 2010. 2:41-47. doi:10.1007/s12095-009-0015-1.
• [74] Pelto M. On identifying and locating-dominating codes in the infinite king grid, PhD thesis, University of Turku, Finland, 2012.
• [75] Pelto M. Maximum difference about the size of optimal identifying codes in graphs differing by one vertex, Discrete Math. Theor. Comput. Sci. 2015. 17(1):339-356. doi:10.46298/dmtcs.2107.
• [76] Rall DF, and Slater PJ. On location-domination numbers for certain classes of graphs, Congr. Numer. 1984. 45:97-106.
• [77]* Ranto S, Honkala I, and Laihonen T. Two families of optimal identifying codes in binary Hamming spaces, IEEE Trans. Inform. Theory 2002. 48:1200-1203.
• [78] Rao NSV. Computational complexity issues in operative diagnosis of graph-based systems, IEEE Trans. Comput. 1993. 42:447-457. doi:10.1109/12.214691.
• [79] Ray S, Ungrangsi R, Pellegrini F De, Trachtenberg A, and Starobinski D. Robust location detection in emergency sensor networks, Proceedings of INFOCOM 2003, San Francisco, USA (2003):1044-1053. doi:10.1109/INFCOM.2003.1208941.
• [80] Rosendahl P. On the identification of vertices using cycles, Electron. J. Combin. 2003. 10(1):R7. doi:10.37236/1700.
• [81] Salo V, and Tӧrmӓ I. Finding codes on infinite grids automatically, to appear in Fund. Inform. 2024. (see also arXiv:2303.00557).
• [82] Seo SJ, and Slater PJ. Open neighborhood locating-dominating sets, Australas. J. Combin. 2010. 46:109-119. ID:15716275.
• [83] Slater PJ. Domination and location in graphs, Research Report No. 93, National University of Singapore 1983.
• [84] Stanton B. Improved bounds for r-identifying codes of the hex grid, SIAM J. Discrete Math. 2011. 25:159-169. doi:10.1137/100791610.
• [85] Stolee D. Automated Discharging Arguments for Density Problems in Grids, arXiv:1409.5922, ID:15143804.