Na wykresie Izomorfizm Kompletne problemy

Jestem zainteresowany badaniem kompletnych problemów z Graph Isomorphism (GI).

W artykule „Problemy wielomianowo równoważne z izomorfizmem grafowym” Kellogga S. Bootha (1979) udowodnili, że wiele podstawowych problemów jest uzupełnionych GI przy użyciu technik zastępowania krawędzi, technik kompozycji itp.

Chciałbym nauczyć się kilku innych technik, które są używane w ostatnich artykułach.

Czy ktoś może mi zasugerować kilka ostatnich artykułów, które są bardziej skoncentrowane na udowodnieniu, że klasa grafów jest ukończona.

cc.complexity-theory reference-request graph-isomorphism

— Kumar
źródło

zobacz także wykres

— vzn

Co zrobiłeś, aby znaleźć takie dokumenty na własną rękę? Czy próbowałeś zastosować standardowe metody wyszukiwania literatury (np. Wyszukiwanie w Google Scholar, znajdowanie wszystkich artykułów cytujących artykuł Booth itp.)?

— DW

Kompletność izomorfizmu grafów dla idealnych wykresów i podklas idealnych wykresów C. Boucher D. Loker (2006)

W tym artykule dowodzimy, że decydujący izomorfizm podwójnie podzielonych grafów, klasa grafów wykazujących połączenie 2 i klasa grafów wykazujących zrównoważony podział skośny są kompletne pod względem GI. Ponadto pokazujemy, że problem GI dla większej klasy obejmującej te klasy grafów - czyli klasę idealnych grafów - jest również kompletny dla GI.

— vzn
źródło

@gold great; wyskoczył na mnie spośród różnych alternatyw częściowo dlatego, że doskonałe wykresy wydają się mieć wiele głębokich powiązań z teorią złożoności i wydają się mieć jeszcze inne duże, jeszcze nie odkryte, ale „na horyzoncie” więzi.

— vzn