Том 24, номер 4, 2017 г., Стр. 22-33

УДК 519.17
Бессонов Ю. Е., Добрынин А. А.
Решёточно полные графы

Аннотация:
Исследуются свойства графов, которые могут быть размещены в прямоугольной решётке на плоскости так, чтобы все вершины, расположенные в одном и том же ряду (горизонтальном или вертикальном), были смежными. Сформулирован критерий принадлежности произвольного графа указанному классу.
Ил. 4, библиогр. 23.

Ключевые слова: граф, прямоугольная решётка, клика.

DOI: 10.17377/daio.2017.24.582

Бессонов Юрий Ефимович ¹
Добрынин Андрей Алексеевич ²
1. Всероссийский институт научной и технической информации РАН,
ул. Усиевича, 20, 125190 Москва, Россия
2. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: bessonov-ye@rambler.ru, dobr@math.nsc.ru

Статья поступила 20 июня 2017 г.
Исправленный вариант — 17 июля 2017 г.

Литература

[1] Бессонов Ю. Е. О решении задачи поиска наибольших пересечений графов на основе анализа проекций подграфов модульного произведения // Вычислительные системы. Новосибирск, 1985. Вып. 112. С. 3–22.

[2] Бессонов Ю. Е. Использование свойств решёточно полных графов для поиска общих подструктур / ВИНИТИ РАН. М., 2014. 13 с. Деп. в ВИНИТИ РАН 03.02.2014, № 32-В2014.

[3] Бессонов Ю. Е. Использование свойств решёточно полных графов для анализа симметрий структур / ВИНИТИ РАН. М., 2014. 18 с. Деп. в ВИНИТИ РАН 10.06.2014, № 169-В2014.

[4] Бессонов Ю. Е., Мищенко Г. Л., Скоробогатов В. А. О задаче выделения скелетных схем химических реакций при построении информационных систем по химии // Науч.-техн. инф. Сер. 2. 1985. № 1.
С. 8–12.

[5] Визинг В. Г. Сведение проблемы изоморфизма и изоморфного вложения к задаче нахождения неплотности // Тр. III Всесоюз. конф. по проблемам теоретической кибернетики. Новосибирск, 1974. С. 124.

[6] Загоруйко Н. Г., Скоробогатов В. А., Хворостов П. В. Вопросы анализа и распознавания молекулярных структур на основе анализа общих фрагментов // Вычислительные системы. Новосибирск, 1984. Вып. 103. С. 26–50.

[7] Akutsu T. A polynomial time algorithm for finding a largest common subgraph of almost trees of bounded degree // IEICE Trans. Fundamentals. 1993. Vol. E76-A, No. 9. P. 1488–1493.

[8] Barrow H. G., Burstall R. M. Subgraph isomorphism, matching relational structures and maximal cliques // Inf. Proc. Lett. 1976. Vol. 4, No. 4. P. 83–84.

[9] Bonnici V., Giugno R., Pulvirenti A., Shasha D., Ferro A. A subgraph isomorphism algorithm and its application to biochemical data // BMC Bioinformatics. 2013. Vol. 14, Suppl. 7, S13. P. 1–13.

[10] Duesbury E., Holliday J. D., Willett P. Maximum common subgraph isomorphism algorithms // MATCH Commun. Math. Comput. Chem. 2017. Vol. 77. P. 213–232.

[11] Ehrlich H. C., Rarey M. Maximum common subgraph isomorphism algorithms and their applications in molecular science: A review // WIREs Comput. Mol. Sci. 2011. Vol. 1. P. 68–79.

[12] Fröhlich H., Košir A., Zajc B. Optimization of FPGA configurations using parallel genetic algorithm // Inf. Sci. 2001. Vol. 133, No. 3. P. 195–219.

[13] Funabiki N., Kitamichi J. A two-stage discrete optimization method for largest common subgraph problems // IEICE Trans. Inf. Syst. 1999. Vol. E82-D, No. 8. P. 1145–1153.

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

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

[16] Harary F. Graph theory. Reading: Addison-Wesley, 1969. 274 p.

[17] Hopcroft J. E., Karp R. M. An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs // SIAM J. Comput. 1973. Vol. 2, No. 4. P. 225–231.

[18] Levi G. A note on the derivation of maximal common subgraphs of two directed or undirected graphs // Calcolo. 1973. Vol. 9, No. 4. P. 341–352.

[19] McGregor J. J. Backtrack search algorithms and the maximal common subgraph problem // Software: Pract. Exper. 1982. Vol. 12. P. 23–34.

[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. 2002. Vol. 42, No. 2. P. 305–316.

[21] Raymond J. W., Willett P. Maximum common subgraph isomorphism algorithms for the matching of chemical structures // J. Comput. Aided Mol. Des. 2002. Vol. 16. P. 521–533.

[22] Ullmann J. R. An algorithm for subgraph isomorphism // J. ACM. 1976. Vol. 16. P. 31–42.

[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. 1994. Vol. 33, No. 11. P. 1189–1192.