Na wykresie Izomorfizm Kompletne problemy

11

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
4
zobacz także wykres
vzn
2
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

Odpowiedzi:

4

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