Проблема изоморфизма для классов графов, инвариантных относительно стягиваний

Рассматривается проблема изоморфизма для графов из классов, которые вместе с каждым графом содержат его связные индуцированные подграфы и графы, полученные с помощью последовательности операций отождествления концов ребра. Основной результат состоит в установлении условий, гарантирующих существование алгоритма полиномиальной сложности для распознавания изоморфизма графов из таких классов. Показано, что невыполнение этих условий приводит к изоморфно-полным классам графов. Библ. – 15 назв.