Geodesic
Lattice complete graphs
Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 4, pp. 22-33.

Voir la notice de l'article provenant de la source Math-Net.Ru

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
Mots-clés : clique. 
@article{DA_2017_24_4_a1,
     author = {Yu. E. Bessonov and A. A. Dobrynin},
     title = {Lattice complete graphs},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {22--33},
     publisher = {mathdoc},
     volume = {24},
     number = {4},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2017_24_4_a1/}
}
TY  - JOUR
AU  - Yu. E. Bessonov
AU  - A. A. Dobrynin
TI  - Lattice complete graphs
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2017
SP  - 22
EP  - 33
VL  - 24
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2017_24_4_a1/
LA  - ru
ID  - DA_2017_24_4_a1
ER  - 
%0 Journal Article
%A Yu. E. Bessonov
%A A. A. Dobrynin
%T Lattice complete graphs
%J Diskretnyj analiz i issledovanie operacij
%D 2017
%P 22-33
%V 24
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2017_24_4_a1/
%G ru
%F DA_2017_24_4_a1
Yu. E. Bessonov; A. A. Dobrynin. Lattice complete graphs. Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 4, pp. 22-33. http://geodesic.mathdoc.fr/item/DA_2017_24_4_a1/

[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”, Computing Systems, 112, Inst. Mat. SO AN SSSR, Novosibirsk, 1985, 3–22 | Zbl

[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, 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, 1985, no. 1, 8–12

[5] V. G. Vizing, “Reduction of the isomorphism and isomorphic embedding problems to the evaluation problem for nondensity of a graph”, Proc. III All-Union Conf. on Problems of Teoretical Cybernetics, Inst. Mat. SO AN SSSR, Novosibirsk, 1974, 124

[6] N. G. Zagoruyko, V. A. Skorobogatov, P. V. Khvorostov, “Topics in the analysis and recognition of molecular structures on the basis of common fragments”, Computing Systems, 103, Inst. Mat. SO AN SSSR, Novosibirsk, 1984, 26–50 | MR

[7] Akutsu T., “A polynomial time algorithm for finding a largest common subgraph of almost trees of bounded degree”, IEICE Trans. Fundamentals, E76-A:9 (1993), 1488–1493

[8] Barrow H. G., Burstall R. M., “Subgraph isomorphism, matching relational structures and maximal cliques”, Inf. Proc. Lett., 4:4 (1976), 83–84 | DOI | Zbl

[9] Bonnici V., Giugno R., Pulvirenti A., Shasha D., Ferro A., “A subgraph isomorphism algorithm and its application to biochemical data”, BMC Bioinformatics, 14, Suppl. 7 (2013), S13, 13 pp. | DOI

[10] Duesbury E., Holliday J. D., Willett P., “Maximum common subgraph isomorphism algorithms”, MATCH Commun. Math. Comput. Chem., 77 (2017), 213–232 | MR

[11] Ehrlich H. C., Rarey M., “Maximum common subgraph isomorphism algorithms and their applications in molecular science: A review”, WIREs Comput. Mol. Sci., 1 (2011), 68–79 | DOI

[12] Fröhlich H., Košir A., Zajc B., “Optimization of FPGA configurations using parallel genetic algorithm”, Inf. Sci., 133:3 (2001), 195–219 | DOI | MR | Zbl

[13] Funabiki N., Kitamichi J., “A two-stage discrete optimization method for largest common subgraph problems”, IEICE Trans. Inf. Syst., E82-D:8 (1999), 1145–1153

[14] Garey M. R., Johnson D. S., Computers and intractability: A guide to the theory of NP-completeness, Freeman, San Francisco, 1979, 338 pp. | MR | Zbl

[15] Grötschel M., Lovász L., Schrijver A., Geometric algorithms and combinatorial optimization, Springer-Verl., Heidelberg, 1988, 362 pp. | MR | Zbl

[16] Harary F., Graph theory, Addison-Wesley, Reading, 1969, 274 pp. | MR | Zbl

[17] Hopcroft J. E., Karp R. M., “An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs”, SIAM J. Comput., 2:4 (1973), 225–231 | DOI | MR | Zbl

[18] Levi G., “A note on the derivation of maximal common subgraphs of two directed or undirected graphs”, Calcolo, 9:4 (1973), 341–352 | DOI | MR | Zbl

[19] McGregor J. J., “Backtrack search algorithms and the maximal common subgraph problem”, Software: Pract. Exper., 12 (1982), 23–34 | DOI | Zbl

[20] Raymond J. W., Gardiner E. J., Willett P., “Heuristics for similarity searching of chemical graphs using a maximum common edge subgraph algorithm”, J. Chem. Inf. Comput. Sci., 42:2 (2002), 305–316 | DOI

[21] Raymond J. W., Willett P., “Maximum common subgraph isomorphism algorithms for the matching of chemical structures”, J. Comput. Aided Mol. Des., 16 (2002), 521–533 | DOI

[22] Ullmann J. R., “An algorithm for subgraph isomorphism”, J. ACM, 16 (1976), 31–42 | DOI | MR

[23] Wagener M., Gasteiger J., “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:11 (1994), 1189–1192 | DOI