О полных задачах об изоморфизме графа

Я заинтересован в изучении полных задач Изоморфизма графов (GI).

В работе Kellogg S. Booth (1979) «Проблемы, полиномиально эквивалентные изоморфизму графа» доказано, что многие базовые задачи являются GI-полными с использованием методов замены краев, методов композиции и т. Д.

Я хотел бы изучить еще несколько методов, которые используются в недавних работах.

Кто-нибудь может предложить мне несколько недавних работ, которые более сконцентрированы на доказательстве того, что некоторый класс графов полон Г.И.

cc.complexity-theory reference-request graph-isomorphism Кумар
источник

см. также полный изоморфизм графов

сложные

Что вы сделали, чтобы попытаться найти такие документы самостоятельно? Пытались ли вы использовать стандартные методы поиска литературы (например, поиск в Google Scholar, поиск всех статей, в которых цитируется статья Бута и т. Д.)?

Ответы:

Полнота изоморфизма графов для совершенных графов и подклассов совершенных графов К. Баучер Д. Локер (2006)

В этой статье мы доказываем, что решающий изоморфизм двойных расщепленных графов, класс графов с 2-соединением и класс графов с сбалансированным косым разбиением являются GI-полными. Далее мы покажем, что задача GI для более крупного класса, включающего эти классы графов, т. Е. Класс совершенных графов, также является GI-полной.

ВЗН
источник

@ золото отличное; он выскочил на меня среди различных альтернатив отчасти потому, что совершенные графы, кажется, имеют много глубоких связей с теорией сложности и, возможно, имеют еще большие, еще не обнаруженные, но "на горизонте" связи.