|
Записки научных семинаров ЛОМИ, 1984, том 137, страницы 99–114
(Mi znsl4789)
|
|
|
|
Полиномиальный алгоритм изоморфизма графов, не стягиваемых на $K_{3,g}$
И. Н. Пономаренко
Аннотация:
В настоящей работе строится полиномиальный алгоритм для проверки изоморфизма графов, не стягиваемых на $K_{3,g}$. При построении используются свойства раскрашенных графов из этого класса и результаты Бабаи-Лакса о канонизации графов. Указанный класс содержит в себе класс графов рода, не превосходящего $g$, и построенный алгоритм применим к распознаванию изоморфизма графов ограниченной валентности. Предложенный метод является обобщением комбинаторного и теоретико-группового подхода к проблеме изоморфизма.
Образец цитирования:
И. Н. Пономаренко, “Полиномиальный алгоритм изоморфизма графов, не стягиваемых на $K_{3,g}$”, Теория сложности вычислений. II, Зап. научн. сем. ЛОМИ, 137, Изд-во «Наука», Ленинград. отд., Л., 1984, 99–114
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl4789 https://www.mathnet.ru/rus/znsl/v137/p99
|
Статистика просмотров: |
Страница аннотации: | 168 | PDF полного текста: | 122 |
|