ENRU
English version: Journal of Applied and Industrial Mathematics, 2017, 11:4, 481485 

Volume 24, No 4, 2017, P. 2233 UDC 519.17
Keywords: graph, rectangular lattice, clique. DOI: 10.17377/daio.2017.24.582 Yuri E. Bessonov ^{1} Received 20 June 2017 References[1] Yu. E. Bessonov, On the solution to the greatest intersection search problem on graphs with the use of analysis of subgraph projections in the modular product of the graphs, Vychislitel’nye sistemy (Computing Systems), Vol. 112, pp. 3–22, Inst. Mat. SO AN SSSR, Novosibirsk, 1985.[2] Yu. E. Bessonov, Using the properties of lattice complete graphs for search of common substructures, Manuscr., Deposited in VINITI RAN 03.02.2014, No. 32B2014, VINITI RAN, Moscow, 2014. [3] Yu. E. Bessonov, Using the properties of lattice complete graphs for analysis of structure symmetries, Manuscr., Deposited in VINITI RAN 10.06.2014, No. 169B2014, VINITI RAN, Moscow, 2014. [4] Yu. E. Bessonov, G. L. Mishchenko, and V. A. Skorobogatov, On the problem of determining skeleton schemes of chemical reactions in the construction of information systems in chemistry, NauchnoTekh. Inf., Ser. 2, 1, 8–12, 1985. [5] V. G. Vizing, Reduction of the isomorphism and isomorphic embedding problems to the evaluation problem for nondensity of a graph, in Trudy III Vsesoyuznoi konferentsii po problemam teoreticheskoi kibernetiki (Proc. III AllUnion Conf. on Problems of Teoretical Cybernetics), p. 124, Inst. Mat. SO AN SSSR, Novosibirsk, 1974. [6] N. G. Zagoruyko, V. A. Skorobogatov, and P. V. Khvorostov, Topics in the analysis and recognition of molecular structures on the basis of common fragments, Vychislitel’nye sistemy (Computing Systems), Vol. 103, pp. 26–50, Inst. Mat. SO AN SSSR, Novosibirsk, 1984. [7] T. Akutsu, A polynomial time algorithm for finding a largest common subgraph of almost trees of bounded degree, IEICE Trans. Fundamentals, E76A, No. 9, 1488–1493, 1993. [8] H. G. Barrow and R. M. Burstall, Subgraph isomorphism, matching relational structures and maximal cliques, Inf. Proc. Lett., 4, No. 4, 83–84, 1976. [9] V. Bonnici, R. Giugno, A. Pulvirenti, D. Shasha, and A. Ferro, A subgraph isomorphism algorithm and its application to biochemical data, BMC Bioinform., 14, Suppl. 7, S13, 1–13, 2013. [10] E. Duesbury, J. D. Holliday, and P. Willett, Maximum common subgraph isomorphism algorithms, MATCH Commun. Math. Comput. Chem., 77, 213–232, 2017. [11] H. C. Ehrlich and M. Rarey, Maximum common subgraph isomorphism algorithms and their applications in molecular science: A review, WIREs Comput. Mol. Sci., 1, 68–79, 2011. [12] H. Fröhlich, A. Košir, and B. Zajc, Optimization of FPGA configurations using parallel genetic algorithm, Inf. Sci., 133, No. 3, 195–219, 2001. [13] N. Funabiki and J. Kitamichi, A twostage discrete optimization method for largest common subgraph problems, IEICE Trans. Inf. Syst., E82D, No. 8, 1145–1153, 1999. [14] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NPCompleteness, Freeman, San Francisco, 1979. [15] M. Grötschel, L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, SpringerVerlag, Heidelberg, 1988 (Algorithms Comb., Vol. 2). [16] F. Harary, Graph Theory, AddisonWesley, Reading, MA, 1969. [17] J. E. Hopcroft and R. M. Karp, An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs, SIAM J. Comput., 2, No. 4, 225–231, 1973. [18] G. Levi, A note on the derivation of maximal common subgraphs of two directed or undirected graphs, Calcolo, 9, No. 4, 341–352, 1973. [19] J. J. McGregor, Backtrack search algorithms and the maximal common subgraph problem, Softw., Pract. Exper., 12, 23–34, 1982. [20] J. W. Raymond, E. J. Gardiner, and P. Willett, Heuristics for similarity searching of chemical graphs using a maximum common edge subgraph algorithm, J. Chem. Inf. Comput. Sci., 42, No. 2, 305–316, 2002. [21] J. W. Raymond and P. Willett, Maximum common subgraph isomorphism algorithms for the matching of chemical structures, J. Comput. Aided Mol. Des., 16, 521–533, 2002. [22] J. R. Ullmann, An algorithm for subgraph isomorphism, J. ACM, 16, 31–42, 1976. [23] M. Wagener and J. Gasteiger, The determination of maximum common substructures by a genetic algorithm: Application in synthesis design and for the structural analysis of biological activity, Angew. Chem. Int. Ed. Engl., 33, No. 11, 1189–1192, 1994. 

© Sobolev Institute of Mathematics, 2015  