Problem izomorfizmu grafu - Graph isomorphism problem
Czy problem izomorfizmu grafów można rozwiązać w czasie wielomianowym?
Problemem wykres Izomorfizm jest obliczeniowa Problem określenia czy dwa skończonych wykresy są izomorficzne .
Nie wiadomo, czy problem jest rozwiązywalny w czasie wielomianowym ani NP-zupełny , a zatem może należeć do klasy złożoności obliczeniowej NP-pośredniej . Wiadomo, że problem izomorfizm grafów jest w niskiej hierarchii z klasy NP , co oznacza, że nie jest NP-zupełny, chyba że wielomian hierarchia czas wali do drugiego poziomu. Jednocześnie izomorfizm dla wielu specjalnych klas grafów można rozwiązać w czasie wielomianowym, a w praktyce izomorfizm grafów często można rozwiązać efektywnie.
Problem ten jest szczególnym przypadkiem problemu izomorfizmu podgrafu , który pyta, czy dany graf G zawiera podgraf, który jest izomorficzny z innym danym grafem H ; wiadomo, że problem ten jest NP-zupełny. Wiadomo również, że jest to szczególny przypadek problemu ukrytej podgrupy nieabelowej nad grupą symetryczną .
W dziedzinie rozpoznawania obrazów jest to znane jako dokładne dopasowanie wykresu .
Najnowocześniejszy
W listopadzie 2015 r. László Babai ogłosił algorytm czasu quasi-wielomianowego dla wszystkich grafów, czyli taki z czasem działania dla niektórych stałych . W dniu 4 stycznia 2017 r. Babai wycofał twierdzenie quasi-wielomianowe i zamiast tego podał wykładniczy limit czasu po tym, jak Harald Helfgott odkrył błąd w dowodzie. 9 stycznia 2017 r. Babai ogłosił korektę (opublikowaną w całości 19 stycznia) i przywrócił roszczenie quasi-wielomianowe, a Helfgott potwierdził poprawkę. Helfgott dalej twierdzi, że można przyjąć c = 3 , więc czas wykonania wynosi 2 O((log n ) 3 ) .
Wcześniej najlepszy algorytm teoretyczna obecnie akceptowane było spowodowane Babai & Luks (1983) , a opiera się na wcześniejszych pracach przez Luks (1982) w połączeniu z subfactorial algorytmu VN Zemlyachenko ( Zemlyachenko, Korneenko & Tyshkevich 1985 ). Algorytm ma czas wykonania 2 O( √ n log n ) dla grafów o n wierzchołkach i opiera się na klasyfikacji skończonych grup prostych . Bez tego twierdzenia klasyfikacyjnego, nieco słabsze ograniczenie 2 O ( √ n log 2 n ) zostało uzyskane najpierw dla silnie regularnych grafów przez László Babai ( 1980 ), a następnie rozszerzone na ogólne grafy przez Babai i Luksa (1983) . Poprawa wykładnika √ n jest głównym otwartym problemem; dla silnie regularnych grafów dokonał tego Spielman (1996) . Dla hipergrafów o ograniczonej randze, podwykładnicza górna granica pasująca do przypadku grafów została uzyskana przez Babai i Codenotti (2008) .
Istnieje kilka konkurujących ze sobą praktycznych algorytmów izomorfizmu grafów, takich jak te opracowane przez McKaya (1981) , Schmidta i Druffela (1976) oraz Ullmana (1976) . Chociaż wydają się dobrze działać na losowych wykresach , główną wadą tych algorytmów jest ich wykładnicza wydajność w czasie w najgorszym przypadku .
Problem izomorfizmu grafu jest obliczeniowo równoważny z problemem obliczania grupy automorfizmu grafu i jest słabszy niż problem izomorfizmu grup permutacji i problem przecięcia grup permutacji. W przypadku tych dwóch ostatnich problemów Babai, Kantor i Luks (1983) uzyskali ograniczenia złożoności podobne do tych dla izomorfizmu grafów.
Rozwiązane szczególne przypadki
Szereg ważnych szczególnych przypadków problemu izomorfizmu grafów ma efektywne rozwiązania wielomianowe:
- Drzewa
- Grafy planarne (w rzeczywistości izomorfizm grafów planarnych jest w przestrzeni logarytmicznej , klasa zawarta w P )
- Wykresy interwałowe
- Wykresy permutacji
- Wykresy cyrkulacyjne
- Wykresy o ograniczonych parametrach
- Wykresy ograniczonej szerokości drzewa
- Wykresy ograniczonego rodzaju (wykresy planarne to wykresy rodzaju 0).
- Wykresy stopnia ograniczonego
- Wykresy z ograniczoną krotnością wartości własnych
- k – Grafy kurczliwe (uogólnienie ograniczonego stopnia i ograniczonego rodzaju)
- Zachowujący kolor izomorfizm kolorowych grafów z ograniczoną krotnością kolorów (tzn. co najwyżej k wierzchołków ma ten sam kolor dla ustalonego k ) należy do klasy NC , która jest podklasą P
Klasa złożoności GI
Ponieważ problem izomorfizmu grafu nie jest ani znany jako NP-zupełny, ani jako wykonalny, naukowcy starali się uzyskać wgląd w ten problem, definiując nową klasę GI , zbiór problemów z wielomianową redukcją Turinga do izomorfizmu grafu problem. Jeśli w rzeczywistości problem izomorfizmu grafów jest rozwiązywalny w czasie wielomianowym, GI równałoby się P . Z drugiej strony, jeśli problem jest NP-zupełny, GI będzie równe NP, a wszystkie problemy w NP będą rozwiązywalne w czasie quasi-wielomianowym.
Jak to jest typowe dla klas złożoności w hierarchii czasu wielomianowego , problem nazywa się GI-trudny, jeśli istnieje redukcja Turinga w czasie wielomianowym z dowolnego problemu w GI do tego problemu, tj. rozwiązanie wielomianowe dla trudnego problemu GI dałoby wielomianowe rozwiązanie problemu izomorfizmu grafu (a więc wszystkich problemów w GI ). Problem nazywa się kompletnym dla GI lub GI-complete , jeśli jest zarówno trudny dla GI , jak i wielomianowe rozwiązanie problemu GI dałoby rozwiązanie wielomianowe dla .
Problem izomorfizmu grafów zawarty jest zarówno w NP, jak i co- AM . GI jest zawarte i niskie dla parytetu P , a także zawarte w potencjalnie znacznie mniejszej klasie SPP . To, że leży on w parzystości P, oznacza, że problem izomorfizmu grafów nie jest trudniejszy niż ustalenie, czy niedeterministyczna maszyna Turinga w czasie wielomianowym ma parzystą czy nieparzystą liczbę akceptujących ścieżek. GI jest również zawarty i niski dla ZPP NP . Zasadniczo oznacza to, że wydajny algorytm Las Vegas z dostępem do wyroczni NP może tak łatwo rozwiązać izomorfizm grafów, że nie zyskuje żadnej mocy, gdy ma możliwość robienia tego w stałym czasie.
GI-kompletne i GI-trudne problemy
Izomorfizm innych obiektów
Istnieje wiele klas obiektów matematycznych, dla których problem izomorfizmu jest problemem GI-zupełnym. Szereg z nich to wykresy posiadające dodatkowe właściwości lub ograniczenia:
- dwuznaki
- grafy etykietowane , z zastrzeżeniem, że do zachowania etykiet nie jest wymagany izomorfizm, a jedynie relacja równoważności składająca się z par wierzchołków o tej samej etykiecie
- „grafy spolaryzowane” (złożone z grafu pełnego K m i grafu pustego K n plus kilka krawędzi łączących oba; ich izomorfizm musi zachować podział)
- 2- kolorowe wykresy
- jawnie dane struktury skończone
- multigrafy
- hipergrafy
- automaty skończone
- Procesy decyzyjne Markowa
- przemienna klasa 3 nilpotent (tj. xyz = 0 dla każdego elementu x , y , z ) półgrupy
- algebry asocjacyjne o skończonych szeregach nad ustalonym ciałem algebraicznie domkniętym z pierwiastkiem zerowym do kwadratu i współczynnikiem przemiennym nad pierwiastkiem.
- gramatyki bezkontekstowe
- zrównoważone niekompletne projekty blokowe
- Uznając kombinatorycznej izomorfizm z wypukłymi polytopes przedstawionych przypadków wierzchołek-kręgowych.
GI-kompletne klasy grafów
Klasa grafów nosi nazwę GI-complete, jeśli rozpoznawanie izomorfizmu dla grafów z tej podklasy jest problemem GI-complete. Następujące klasy są kompletne GI:
- połączone wykresy
- wykresy średnicy 2 i promienia 1
- skierowane grafy acykliczne
- regularne wykresy
- grafy dwudzielne bez nietrywialnych podgrafów silnie regularnych
- dwudzielne grafy Eulera
- dwudzielne grafy regularne
- wykresy liniowe
- podzielone wykresy
- wykresy akordowe
- regularne grafy samouzupełniające się
- grafy politopowe ogólnych, prostych i uproszczonych politopów wypukłych w dowolnych wymiarach.
Wiele klas dwuznaków jest również kompletnych GI.
Inne problemy z całkowitym GI
Oprócz problemów z izomorfizmem istnieją inne nietrywialne problemy z całkowitym GI.
- Rozpoznanie samokomplementarności grafu lub digrafu.
- Problem kliki do klasy tak zwanych M -graphs. Pokazano, że znalezienie izomorfizmu dla grafów o n- wierzchołkach jest równoważne znalezieniu n- kliki w M- grafie o rozmiarze n 2 . Fakt ten jest interesujący, ponieważ problem znalezienia ( n − ε )-kliki w M- grafie o rozmiarze n 2 jest NP-zupełny dla dowolnie małych dodatnich ε.
- Problem homeomorfizmu 2-kompleksów.
Problemy z GI
- Problem zliczania izomorfizmów między dwoma grafami jest równoważny w czasie wielomianowym z problemem stwierdzenia, czy w ogóle taki istnieje.
- Problem rozstrzygnięcia, czy dwa politopy wypukłe podane w opisie V lub H są izomorficzne projekcyjnie, czy afinicznie. To ostatnie oznacza istnienie mapy rzutowej lub afinicznej między przestrzeniami, które zawierają dwa politopy (niekoniecznie o tym samym wymiarze), co powoduje bijekcję między politopami.
Sprawdzanie programu
Manuel Blum i Sampath Kannan ( 1995 ) pokazali probabilistyczny kontroler dla programów izomorfizmu grafów. Załóżmy, że P jest deklarowaną procedurą wielomianową, która sprawdza, czy dwa grafy są izomorficzne, ale nie jest zaufana. Aby sprawdzić, czy G i H są izomorficzne:
- Zapytaj P, czy G i H są izomorficzne.
- Jeśli odpowiedź brzmi „tak”:
- Próba skonstruowania izomorfizmu przy użyciu P jako podprogramu. Zaznacz wierzchołek u w G i v w H i zmodyfikuj wykresy tak, aby były wyróżniające się (z niewielką zmianą lokalną). Zapytaj P, czy zmodyfikowane wykresy są izomorficzne. Jeśli nie, zmień v na inny wierzchołek. Kontynuuj wyszukiwanie.
- Albo izomorfizm zostanie znaleziony (i można go zweryfikować), albo P będzie sobie zaprzeczać.
- Jeśli odpowiedź brzmi „nie”:
- Wykonaj następujące 100 razy. Wybierz losowo G lub H i losowo permutuj jego wierzchołki. Zapytaj P, czy wykres jest izomorficzny z G i H . (Jak w protokole AM dla nieizomorfizmu grafu).
- Jeśli którykolwiek z testów nie powiedzie się, osądź P jako nieprawidłowy program. W przeciwnym razie odpowiedz „nie”.
- Jeśli odpowiedź brzmi „tak”:
Ta procedura jest wielomianowa i daje poprawną odpowiedź, jeśli P jest poprawnym programem dla izomorfizmu grafów. Jeśli P nie jest poprawnym programem, ale odpowiada poprawnie na G i H , sprawdzający albo poda poprawną odpowiedź, albo wykryje nieprawidłowe zachowanie P . Jeśli P nie jest poprawnym programem i odpowiada niepoprawnie na G i H , kontroler wykryje nieprawidłowe zachowanie P z dużym prawdopodobieństwem lub odpowie błędnie z prawdopodobieństwem 2 −100 .
Warto zauważyć, że P jest używany tylko jako czarna skrzynka.
Aplikacje
Wykresy są powszechnie używane do kodowania informacji strukturalnych w wielu dziedzinach, w tym w zakresie wizji komputerowej i rozpoznawania wzorców , a dopasowywanie wykresów , czyli identyfikacja podobieństw między wykresami, jest ważnym narzędziem w tych obszarach. W tych obszarach problem izomorfizmu grafów nazywany jest dokładnym dopasowaniem grafów.
W cheminformatyce i chemii matematycznej testowanie izomorfizmu grafów jest wykorzystywane do identyfikacji związku chemicznego w chemicznej bazie danych . Również w organicznej chemii matematycznej testowanie izomorfizmu grafów jest przydatne do generowania grafów molekularnych i syntezy komputerowej .
Przeszukiwanie baz danych chemicznych jest przykładem graficznej eksploracji danych , w której często stosuje się podejście do kanonizacji grafów . W szczególności, liczba identyfikatorów dla substancji chemicznych , takich jak SMILES i Inchi , mające na celu zapewnienie wzorca i czytelnej dla człowieka sposób kodowania informacji molekularnej i ułatwienia wyszukiwania tych informacji w bazie danych informacji na stronie, etap wykorzystania kanonizacyjnego w ich obliczenia, które są zasadniczo kanonizacją wykresu reprezentującego cząsteczkę.
W projektowaniu układów elektronicznych izomorfizm grafów jest podstawą etapu projektowania obwodu Layout Versus Schematic (LVS), który polega na weryfikacji, czy obwody elektryczne reprezentowane przez schemat obwodu i układ układu scalonego są takie same.
Zobacz też
Uwagi
Bibliografia
- Aho, Alfred V. ; Hopcroft, Jan ; Ullman, Jeffrey D. (1974), Projektowanie i analiza algorytmów komputerowych , Reading, MA: Addison-Wesley.
- Arvinda, Vikramana; Köbler, Johannes (2000), „Izomorfizm wykresu jest niski dla ZPP(NP) i innych wyników niskiej jakości.”, Proceedings of 17th Annual Symposium on Theoretical Aspects of Computer Science , Lecture Notes in Computer Science , 1770 , Springer-Verlag, s. . 431-442 , doi : 10.1007 / 3-540-46541-3_36 , ISBN 3-540-67141-2, MR 1781752.
- Arvinda, Vikramana; Kurur, Piyush P. (2006), „Izomorfizm wykresu jest w SPP”, Informacje i obliczenia , 204 (5): 835-852, doi : 10.1016/j.ic.2006.02.002 , MR 2226371.
- Babai, László (1980), „O złożoności kanonicznego etykietowania silnie regularnych wykresów”, SIAM Journal on Computing , 9 (1): 212-216, doi : 10.1137/0209018 , MR 0557839.
- Babai, László ; Codenotti, Paolo (2008), „Izomorfizm hipergrafów niskiej rangi w umiarkowanie wykładniczym czasie” (PDF) , Proceedings of 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008) , IEEE Computer Society, s. 667-676, doi : 10.1109/FOCS.2008.80 , ISBN 978-0-7695-3436-7, S2CID 14025744.
- Babai, László ; Grigoryev, D. Yu. ; Mount, David M. (1982), „Izomorfizm grafów z ograniczoną krotnością wartości własnych”, Proceedings of 14th Annual ACM Symposium on Theory of Computing , str. 310-324, doi : 10.1145/800070.802206 , ISBN 0-89791-070-2, S2CID 12837287.
- Babai, László ; Kantor, William ; Luks, Eugene (1983), „Computational complex and the Classification of finite simple groups”, Proceedings of 24th Annual Symposium on Foundations of Computer Science (FOCS) , s. 162-171, doi : 10.1109/SFCS.1983.10 , S2CID 6670135.
- Babai, László ; Luks, Eugene M. (1983), "Canonical labeling of graphs", Proceedings of the piętnastym dorocznym sympozjum ACM on Theory of Computing (STOC '83) , s. 171-183, doi : 10.1145/800061.808746 , ISBN 0-89791-099-0, S2CID 12572142.
- Babai, László (2015), Izomorfizm wykresu w czasie quasipolimianial , arXiv : 1512.03547 , Bibcode : 2015arXiv151203547B
- Baird, HS; Cho, YE (1975), "System weryfikacji projektu graficznego" , Proceedings of 12th Design Automation Conference (DAC '75) , Piscataway, NJ, USA: IEEE Press, s. 414-420.
- Blum, Manuel ; Kannan, Sampath (1995), „Projektowanie programów sprawdzających swoją pracę” , Journal of the ACM , 42 (1): 269–291, CiteSeerX 10.1.1.38.2537 , doi : 10.1145/200836.200880 , S2CID 52151779.
- Bodlaender, Hans (1990), „Algorytmy wielomianowe dla izomorfizmu grafów i indeksu chromatycznego na cząstkowych k- drzew”, Journal of Algorithms , 11 (4): 631-643, doi : 10.1016/0196-6774(90)90013-5 , MR 1079454.
- Booth, Kellogg S.; Colbourn, CJ (1977), Problemy wielomianowo równoważne izomorfizmowi grafu , Raport techniczny, CS-77-04, Wydział Informatyki, Uniwersytet Waterloo.
- Booth, Kellogg S.; Lueker, George S. (1979), „Algorytm czasu liniowego decydującego o izomorfizmie wykresu przedziałowego” , Journal of the ACM , 26 (2): 183-195, doi : 10.1145/322123.322125 , MR 0528025 , S2CID 18859101.
- Boucher, C.; Loker, D. (2006), Kompletność izomorfizmu grafów dla doskonałych grafów i podklas doskonałych grafów (PDF) , Raport techniczny, CS-2006-32, Wydział Informatyki, Uniwersytet Waterloo.
- Chung, Fan RK (1985), „O szerokości cięcia i topologicznej przepustowości drzewa”, SIAM Journal on Algebraic and Discrete Methods , 6 (2): 268-277, doi : 10.1137/0606026 , MR 0778007.
- Colbourn, CJ (1981), „Na testowaniu izomorfizmu wykresów permutacji”, Sieci , 11 : 13-21, doi : 10.1002/net.3230110103 , MR 0608916.
- Colbourn, Marlene Jones; Colbourn, Charles J. (1978), „Izomorfizm wykresu i grafy samokomplementarne ”, ACM SIGACT News , 10 (1): 25-29, doi : 10.1145/1008605.1008608 , S2CID 35157300.
- Cook, Diane J.; Holder, Lawrence B. (2007), "Sekcja 6.2.1: Canonical Labeling" , Mining Graph Data , Wiley, s. 120-122, ISBN 978-0-470-07303-2.
- Datta, S.; Limaye, N.; Nimbhorkar, P.; Thierauf, T.; Wagner, F. (2009), „Izomorfizm grafów planarnych jest w przestrzeni logarytmicznej”, 24th Annual IEEE Conference on Computational Complexity 2009 , s. 203, arXiv : 0809.2319 , doi : 10.1109/CCC.2009.16 , ISBN 978-0-7695-3717-7, S2CID 14836820.
- Filotti, IS; Mayer, Jack N. (1980), „Algorytm wielomianowy do określania izomorfizmu grafów ustalonego rodzaju”, Proceedings of the 12th Annual ACM Symposium on Theory of Computing , s. 236–243, doi : 10.1145/800141.804671 , Numer ISBN 0-89791-017-6, S2CID 16345164.
- Foggia, P.; Sansone, C.; Vento, M. (2001), „Porównanie wydajności pięciu algorytmów izomorfizmu grafów” (PDF) , Proc. III Warsztaty IAPR-TC15 Reprezentacje grafowe w rozpoznawaniu wzorców , s. 188–199.
- Garey, Michael R .; Johnson, David S. (1979), Komputery i niewykonalność: przewodnik po teorii NP-zupełności , WH Freeman, ISBN 978-0-7167-1045-5.
- Grigoriew, D. Ju. (1981), „Złożoność 'dzikich' problemów macierzowych oraz izomorfizmu algebr i grafów”, Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta Imeni VA Steklova Akademii Nauk SSSR (LOMI) (po rosyjsku), 105 : 10–17, 198 , MR 0628981. Tłumaczenie angielskie w Journal of Mathematical Sciences 22 (3): 1285–1289, 1983.
- Hopcroft, Jan ; Wong, J. (1974), „Liniowy algorytm czasu dla izomorfizmu grafów planarnych”, Proceedings of the Sixth Annual ACM Symposium on Theory of Computing , str. 172-184, doi : 10.1145/800119.803896 , S2CID 15561884.
- Irniger, Christophe-André Mario (2005), Graph Matching: Filtrowanie baz danych wykresów za pomocą uczenia maszynowego , Dissertationen zur künstlichen Intelligenz, 293 , AKA, ISBN 1-58603-557-6.
- Kaibel, Volker; Schwartz, Alexander (2003), „O złożoności problemów izomorfizmu politopów ” , Wykresy i kombinatoryka , 19 (2): 215-230, arXiv : math/0106093 , doi : 10.1007/s00373-002-0503-y , MR 1996205 , S2CID 179936 , zarchiwizowane od oryginału 21.07.2015 r..
- Kelly, Paul J. (1957), "Twierdzenie kongruencji dla drzew", Pacific Journal of Mathematics , 7 : 961-968, doi : 10.2140/pjm.1957.7.961 , MR 0087949.
- Köblera, Johannesa; Schöninga, Uwe ; Torán, Jacobo (1992), „Izomorfizm wykresu jest niski dla PP”, Złożoność obliczeniowa , 2 (4): 301-330, doi : 10.1007/BF01200427 , MR 1215315 , S2CID 8542603.
- Kozen, Dexter (1978), „Klik problem równoważny izomorfizmowi wykresu”, ACM SIGACT News , 10 (2): 50-52, doi : 10.1145/990524.990529 , S2CID 52835766.
- Luks, Eugene M. (1982), „Izomorfizm wykresów ograniczonej wartościowości można testować w czasie wielomianowym”, Journal of Computer and System Sciences , 25 : 42-65, doi : 10.1016/0022-0000 (82) 90009-5 , numer MR 0685360 , S2CID 2572728.
- Luks, Eugene M. (1986), „Algorytmy równoległe dla grup permutacyjnych i izomorfizmu grafów”, Proc. Symp. Podstawy Informatyki , s. 292–302.
- Mathon, Rudolf (1979), „Uwaga na problemie liczenia izomorfizmu wykresu”, Information Processing Letters , 8 (3): 131-132, doi : 10.1016/0020-0190(79)90004-8 , MR 0526453.
- McKay, Brendan D. (1981), „Praktyczny izomorfizm grafu” , 10. Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, 1980) , Congressus Numerantium, 30 , s. 45-87, MR 0635936.
- Miller, Gary (1980), „Isomorphism testing for graphs of bounded genus”, Proceedings of 12th Annual ACM Symposium on Theory of Computing , s. 225-235, doi : 10.1145/800141.804670 , ISBN 0-89791-017-6, S2CID 13647304.
- Miller, Gary L. (1983), „Testowanie izomorfizmu i formy kanoniczne dla grafów k- kontraktowalnych (uogólnienie ograniczonej wartościowości i ograniczonego rodzaju)”, Proc. wewn. Konf. o podstawach teorii komputerów , Wykłady z informatyki , 158 , s. 310-327, doi : 10.1007/3-540-12689-9_114. Pełny artykuł w Information and Control 56 (1–2): 1–20, 1983.
- Moore, Cristopher ; Russell, Aleksander; Schulman, Leonard J. (2008), „Symetryczna grupa przeciwstawia się silnemu próbkowaniu Fouriera”, SIAM Journal on Computing , 37 (6): 1842-1864, arXiv : quant-ph/0501056 , doi : 10.1137/050644896 , MR 2386215.
- Muzychuk, Michaił (2004), "Rozwiązanie problemu izomorfizmu dla wykresów obiegowych", Proc. Londyn Matematyka. Soc. , 88 : 1-41, doi : 10.1112/s0024611503014412 , MR 2018956.
- Narayanamurthy, SM; Ravindran, B. (2008), „O twardości znajdowania symetrii w procesach decyzyjnych Markowa” (PDF) , Proceedings of the Twenty-fth International Conference on Machine Learning (ICML 2008) , s. 688-696.
- Schmidt, Douglas C.; Druffel, Larry E. (1976), „Algorytm szybkiego śledzenia wstecznego do testowania skierowanych wykresów izomorfizmu przy użyciu macierzy odległości”, Journal of the ACM , 23 (3): 433-445, doi : 10.1145/321958.321963 , MR 0411230 , S2CID 6163956.
- Schöning, Uwe (1987), „Izomorfizm wykresu znajduje się w niskiej hierarchii”, Proceedings of 4th Annual Symposium on Theoretical Aspects of Computer Science , s. 114-124; także Journal of Computer and System Sciences 37 : 312-323, 1988.
- Shawe-Taylor, John; Pisanski, Tomaž (1994), „Homeomorfizm 2-kompleksów jest izomorfizmem grafu kompletny”, SIAM Journal on Computing , 23 (1): 120-132, doi : 10.1137/S0097539791198900 , MR 1258998.
- Spielman, Daniel A. (1996), „Szybsze testowanie izomorfizmu silnie regularnych grafów”, Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC '96) , ACM, pp. 576-584, ISBN 978-0-89791-785-8.
- Ullman, Julian R. (1976), „Algorytm izomorfizmu podgrafów” (PDF) , Journal of the ACM , 23 : 31-42, CiteSeerX 10.1.1.361.7741 , doi : 10.1145/321921.321925 , MR 0495173 , S2CID 17268751.
Ankiety i monografie
- Czytaj, Ronaldzie C.; Corneil, Derek G. (1977), „Choroba izomorfizmu wykresu”, Journal of Graph Theory , 1 (4): 339-363, doi : 10.1002/jgt.3190010410 , MR 0485586.
- Gati, G. (1979), „Dalsze adnotacje bibliografia na temat choroby izomorfizmu”, Journal of Graph Theory , 3 (2): 95-109, doi : 10.1002/jgt.3190030202.
- Zemlyachenko, WN; Korneenko, Nowy Meksyk; Tyszkiewicz, RI (1985), "Problem izomorfizmu wykresu", Journal of Mathematical Sciences , 29 (4): 1426-1481, doi : 10.1007/BF02104746 , S2CID 121818465. (Tłumaczenie z Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. VA Steklova AN SSSR (Zapisy seminariów Leningradzkiego Oddziału Instytutu Matematyki Stekłowa Akademii Nauk ZSRR ), t. 118, s. 83–158, 1982.)
- Arvind, V.; Torán, Jacobo (2005), „Testowanie izomorfizmu: perspektywy i problemy otwarte” (PDF) , Biuletyn Europejskiego Stowarzyszenia Informatyki Teoretycznej , 86 : 66-84. (Krótki przegląd otwartych pytań związanych z problemem izomorfizmu dla grafów, pierścieni i grup.)
- Köblera, Johannesa; Schöninga, Uwe ; Torán, Jacobo (1993), The Graph Isomorphism Problem: jego strukturalna złożoność , Birkhäuser, ISBN 978-0-8176-3680-7. ( Z okładki książki : Książki skupiają się na kwestii złożoności obliczeniowej problemu i przedstawiają kilka ostatnich wyników, które zapewniają lepsze zrozumienie względnej pozycji problemu w klasie NP, jak również w innych klasach złożoności.)
- Johnson, David S. (2005), "The NP-Completeness Column", ACM Transactions on Algorithms , 1 (1): 160-176, doi : 10.1145/1077464.1077476 , S2CID 12604799. (To 24. wydanie Kolumny omawia stan wiedzy w zakresie otwartych problemów z książki Komputery i nierozwiązywalność oraz poprzednie kolumny, w szczególności dotyczące izomorfizmu grafów.)
- Torán, Jacobo; Wagner, Fabian (2009), „Złożoność izomorfizmu grafów planarnych” (PDF) , Biuletyn Europejskiego Stowarzyszenia Informatyki Teoretycznej , 97 , zarchiwizowane z oryginału (PDF) 20.09.2010 , pobrane 2010-06- 03.
Oprogramowanie
- Izomorfizm grafu , przegląd implementacji, Repozytorium Algorytmów Stony Brook .