|
Современная математика и ее приложения, 2015, том 97, статья опубликована в англоязычной версии журнала
(Mi cma421)
|
|
|
|
New invariants for the graph isomorphism problem
A. Gamkrelidzea, L. Varamashvilia, G. Hotzb a Tbilisi Ivane Javakhishvili State University
b Saarland University
Аннотация:
In this paper, we introduce a novel polynomial-time algorithm to
compute graph invariants based on the idea of a modified random
walk on graphs. Though not proved to be a full graph invariant
yet, our method gives the right answer for the graph instances
other well-known methods could not compute (such as special
Fürer gadgets and point-line incidence graphs of finite
projective planes of higher degrees).
Образец цитирования:
A. Gamkrelidze, L. Varamashvili, G. Hotz, “New invariants for the graph isomorphism problem”, Journal of Mathematical Sciences, 218:6 (2016), 754–761
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/cma421
|
Статистика просмотров: |
Страница аннотации: | 66 |
|