Нові інваріанти встановлення ізоморфізму графів

2008;
: pp. 90 – 93
Authors: 

Білаль Раді А’Ґґель Аль-Забі, Керницький А. Б., Лобур М. В., Ткаченко С. П.

Національний університет «Львівська політехніка», кафедра систем автоматизованого проектування

The problem of determining the graph isomorphism on the base of binary reduction trees is considered.

1. Татт У. Теория графов. – М.: Мир, 1988. – 424 с. 2. Berge C. Isomorphism problems for hypergraphs // Mathematical centre tracts. – 1974. – 56. – Р. 3–12. 3. Corneil D.B., Gotlieb C.C. An efficient algorithm for Graph isomorphism // J. of A.C.M. – 1970. – Vol. 17, No. 1. Р. 51–74. 4. Курейчик В.М., Королев А.Г. Об одном алгоритме распознавания изоморфных ориентированных графов. – В кн.: Однородные цифровые вычислительные и интегрирующие структуры, VI, Таганрог, ТРТИ, 1976. – С. 94–102. 5. Харари Ф. Теория графов. – М.: Мир, 1973. – 302 с. 6. Земляченко В.Н., Корниенко Н.М., Тышкевич Р.И. Проблема изоморфизма графов // Теория сложности вычислений, I. Записки научных семинаров ЛОМИ. – 1982. – Т. 118. – С. 83–158. 7. Кани К., Оцуки Т. Применение теории графов и комбинаторных алгоритмов в автоматизации проектирования // Дзехо сери. – 1975. – Т. 16, № 17. – С. 581–590. (яп.) 8. Proskurowski A. Automatic generation of graphs and graphs identification problem // Technical Report. – april 1974. – N 16. 9. McCarthy M.K., Davida G.J. Invariant features and the graph isomorphism problem // IEEE Syst. Man and Cybern. Soc. Proc. Int. Conf. Cybern and Soc. – Boston, Mass., 1973. – Р. 81–85. 10. Рейнгольд Э., Нивергельд Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. – М.: Мир, 1980. – 476 с. 11. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. – М.: Мир, 1981. – 368 с. 12. A’Ggel B.R. Al-Zabi, Kernytskyy A., Lobur M., Tkachenko S. On Graph Isomorphism Determining Problem // IEEE MEMSTECH’2008. – Polyana, 2008. – Р. 84. 13. Базилевич Р.П., Ткаченко С.П. Решение задачи разбиения методом параллельного свертывания: В кн.: Вычислительная техника, VI. – Каунас: КПИ, 1975. – С. 295–298. 14. Аль-Забі Б., Керницький А.Б., Ткаченко С.П. Встановлення існування необхідних умов еквівалентності схем // Вісн. Нац. ун-ту “Львівська політехніка”. – 2007. – № 591: Комп’ютерні системи проектування. Теорія і практика. – С. 87–90.