About Journal 
Editorial Board
Publishing Ethics
Author Guide 
Submission
Prepare Your Manuscript
Peer review
Archive
Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2017, 11:4, 481-485
Volume 24, No 4, 2017, P. 22-33
UDC 519.17
Yu. E. Bessonov and A. A. Dobrynin
Lattice complete graphs
Abstract:
We study the properties of graphs that can be placed in a rectangular lattice so that all vertices located in the same (horizontal or vertical) row be adjacent. Some criterion is formulated for an arbitrary graph to be in the specified class.
Illustr. 4, bibliogr. 23.
Keywords: graph, rectangular lattice, clique.
DOI: 10.17377/daio.2017.24.582
Yuri E. Bessonov 1
Andrey A. Dobrynin 2
1. All-Russian Institute for Scientific and Technical Information,
20 Usievich St., 125190 Moscow, Russia
2. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: bessonov-ye@rambler.ru, dobr@math.nsc.ru
Received 20 June 2017
Revised 17 July 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. 32-B2014, 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. 169-B2014, 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, Nauchno-Tekh. 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 All-Union 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, E76-A, 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 two-stage discrete optimization method for largest common subgraph problems, IEICE Trans. Inf. Syst., E82-D, No. 8, 1145–1153, 1999.
[14] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979.
[15] M. Grötschel, L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, Heidelberg, 1988 (Algorithms Comb., Vol. 2).
[16] F. Harary, Graph Theory, Addison-Wesley, 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.
