Problem izomorfizmu grafu - Graph isomorphism problem

Nierozwiązany problem w informatyce :

Czy problem izomorfizmu grafów można rozwiązać w czasie wielomianowym?

(więcej nierozwiązanych problemów w informatyce)

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$ $)$ . ${\ Displaystyle 2 ^ {O ((\ log n) ^ {c})}}$ $c>0$

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 (\sqrt 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 . ${\ Displaystyle X}$ ${\ Displaystyle X}$

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 ² . Fakt ten jest interesujący, ponieważ problem znalezienia ( n − ε )-kliki w M- grafie o rozmiarze n ² 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”.

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 ⁻¹⁰⁰ .

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 .

Languages

In other projects