|
Записки научных семинаров ЛОМИ, 1988, том 174, страницы 147–177
(Mi znsl4516)
|
|
|
|
Эта публикация цитируется в 32 научных статьях (всего в 32 статьях)
Проблема изоморфизма для классов графов, инвариантных относительно стягиваний
И. Н. Пономаренко
Аннотация:
Рассматривается проблема изоморфизма для графов из классов, которые вместе с каждым графом содержат его связные индуцированные подграфы и графы, полученные с помощью последовательности операций отождествления концов ребра. Основной результат состоит в установлении условий, гарантирующих существование алгоритма полиномиальной сложности для распознавания изоморфизма графов из таких классов. Показано, что невыполнение этих условий приводит к изоморфно-полным классам графов. Библ. – 15 назв.
Образец цитирования:
И. Н. Пономаренко, “Проблема изоморфизма для классов графов, инвариантных относительно стягиваний”, Теория сложности вычислений. 3, Зап. научн. сем. ЛОМИ, 174, Изд-во «Наука», Ленинград. отд., Л., 1988, 147–177; J. Soviet Math., 55:2 (1991), 1621–1643
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl4516 https://www.mathnet.ru/rus/znsl/v174/p147
|
Статистика просмотров: |
Страница аннотации: | 255 | PDF полного текста: | 179 |
|