(24) 27 * << * >> * Русский * English * Содержание * Все выпуски

О ВЫЧИСЛИТЕЛЬНОЙ ЭФФЕКТИВНОСТИ АЛГОРИТМА СПЕКТРАЛЬНОГО РАСЩЕПЛЕНИЯ ПРОВЕРКИ ИЗОМОРФИЗМА ГРАФОВ
А.В. Пролубников, Р.Т. Файзулли
Омский государственный университет

 PDF, 272 kB

Страницы: 136-143.

Язык статьи: Русский.

Аннотация:
Мы рассматриваем эвристический алгоритм проверки изоморфизма графов. Алгоритм основан на последовательном расщеплении кратных собственных значений матриц, сопоставленных графам: матрицы, с которыми работает алгоритм, представляют собой модификации матриц смежности графов. Алгоритм строится на последовательном возмущении матриц и решении связанных с ними систем линейных алгебраических уравнений. Матрицы видоизменёны до положительно определенных, что позволяет решать системы линейных уравнений, связанные с ними. Доказывается вычислительная эффективность алгоритма в одной из принципиально тяжелых для решения задачи проверки изоморфизма графов ситуаций.

Keywords:
spectral splitting, graph isomorphism, heuristic algorithm, matrix, linear algebraic equation

Citation:
Prolubnikov AV, Faizullin RT. On the computational efficiency of the spectral splitting algorithm for checking graph isomorphism. Computer Optics 2002; 24: 136-143.

Литература:

  1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи // М.: Мир, 1982.
  2. Цветкович Д. и др. Спектры графов. Теория и применение // Киев: Наукова думка, 1984.
  3. Кикина А.Ю., Файзуллин Р.Т. Алгоритм проверки изоморфности графов // деп. ВИНИТИ 21.06.95 1789-В95.
  4. Hopcroft, Wong. A linear time algorithm for isomorphism of planar graphs// Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, p. 172-184, 1974.
  5. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial time // Proceedings of the 21-st IEEE FOCS Symp., 42, 49, 1980.
  6. Hoffmann. Group-Theoretic Algorithms and Graph Isomorphism// Lecture Notes in Computer Science (Chapter V). P.127-138, 1982.
  7. Беллман Р. Введение в теорию матриц // Москва: Наука, 1976.
  8. Пролубников А.В., Файзуллин Р.Т. Эвристический алгоритм дешифрования шифра двойной перестановки // Математические структуры и моделирование: Сб. научн. тр. Под ред. А.К. Гуца. Омск: Омск. гос. ун-т, 2002. Вып. 9.

© 2009, IPSI RAS
Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: journal@computeroptics.ru; тел: +7 (846) 242-41-24 (ответственный секретарь), +7 (846) 332-56-22 (технический редактор), факс: +7 (846) 332-56-20