Problém isomorfismu grafu - Graph isomorphism problem

Nevyřešený problém v informatice :

Lze problém izomorfismu grafu vyřešit v polynomiálním čase?

(více nevyřešených problémů v informatice)

Problém grafu izomorfismus je výpočetní problém určit, zda dvě konečné grafy jsou izomorfní .

Problém není znám jako řešitelný v polynomiálním čase ani jako NP-úplný , a proto může být ve třídě výpočetní složitosti NP-střední . Je známo, že tento problém graf izomorfismus je v nízké hierarchii z třídy NP , což znamená, že to není NP-úplný, pokud polynom čas hierarchie se zhroutí do druhé úrovně. Současně lze izomorfismus pro mnoho speciálních tříd grafů řešit v polynomiálním čase a v praxi lze často efektivně řešit izomorfismus grafů.

Tento problém je zvláštním případem problému izomorfismu podgrafu , který se ptá, zda daný graf G obsahuje podgraf, který je izomorfní k jinému danému grafu H ; tento problém je znám jako NP-úplný. Je také známo, že jde o speciální případ problému neabelských skrytých podskupin nad symetrickou skupinou .

V oblasti rozpoznávání obrazu je známý jako přesná shoda grafu .

Nejmodernější

V listopadu 2015 László Babai oznámil algoritmus kvazipolynomiálního času pro všechny grafy, tedy ten, který má u některých grafů čas běhu . 4. ledna 2017 Babai zatáhl kvazi-polynomiální tvrzení a místo toho uvedl subexponenciální časový limit poté, co Harald Helfgott objevil chybu v důkazu. Dne 9. ledna 2017 oznámil Babai opravu (publikovanou v plném rozsahu 19. ledna) a obnovil kvazi-polynomiální tvrzení, přičemž opravu potvrdil Helfgott. Helfgott dále tvrdí, že lze vzít $c$ $= 3$ , takže doba běhu je $2$ $O ((log$ $n$ $)$ $3$ $)$ . ${\ Displaystyle 2^{O ((\ log n)^{c})}}$ ${\ displaystyle c> 0}$

Předtím byl v současné době nejlépe přijatým teoretickým algoritmem program Babai & Luks (1983) a vychází z dřívější práce Luksa (1982) v kombinaci se subfaktoriálním algoritmem VN Zemlyachenko ( Zemlyachenko, Korneenko & Tyshkevich 1985 ). Algoritmus má dobu běhu 2 ^{O ( √ n log n )} pro grafy s n vrcholy a spoléhá na klasifikaci konečných jednoduchých skupin . Bez této klasifikace věty, o něco slabší vázaný $2 O (\sqrt n log 2 N)$ se získá nejprve pro silně pravidelné grafy podle László Babai ( 1980 ), a pak se rozšíří na obecné graf podle Babai & Luks (1983) . Zlepšení exponentu √ n je hlavní otevřený problém; u silně pravidelných grafů to provedl Spielman (1996) . Pro hypergrafy s ohraničeným hodnocením byla získána subexponenciální horní hranice odpovídající případu grafů od Babai & Codenotti (2008) .

Pro izomorfismus grafů existuje několik konkurenčních praktických algoritmů, například algoritmy McKay (1981) , Schmidt & Druffel (1976) a Ullman (1976) . I když se zdá, že fungují dobře na náhodných grafech , hlavní nevýhodou těchto algoritmů je jejich exponenciální časový výkon v nejhorším případě .

Problém izomorfismu grafu je výpočetně ekvivalentní problému výpočtu skupiny automorfismu grafu a je slabší než problém izomorfismu skupiny permutací a problém průniku skupiny permutací. U posledních dvou problémů získali Babai, Kantor a Luks (1983) hranice složitosti podobné hranicím pro grafový izomorfismus.

Vyřešeny speciální případy

Řada důležitých zvláštních případů problému izomorfismu grafu má účinná řešení v polynomiálním čase:

Stromy
Rovinné grafy (Ve skutečnosti je izomorfismus planárních grafů v prostoru logu , třída obsažená v P )
Intervalové grafy
Permutační grafy
Oběžné grafy
Grafy ohraničených parametrů
- Grafy ohraničené šířky stromu
- Grafy ohraničeného rodu (planární grafy jsou grafy rodu 0.)
- Grafy ohraničeného stupně
- Grafy s omezenou multiplicitou vlastních čísel
- k -Stažitelné grafy (zobecnění ohraničeného stupně a ohraničeného rodu)
- Izomorfismus barev zachovávajících barevné grafy s omezenou barevnou multiplicitou (tj. Nanejvýš k vrcholů má stejnou barvu pro pevné k ) je ve třídě NC , což je podtřída P

Třída složitosti GI

Vzhledem k tomu, že problém izomorfismu grafu není znám ani jako NP-úplný, ani není znám jako traktovatelný, vědci se snažili získat vhled do problému definováním nové třídy GI , souboru problémů s polynomiální časovou Turingovou redukcí na grafový izomorfismus problém. Pokud ve skutečnosti problém grafu izomorfismus je řešitelná v polynomiálním čase, GI by se rovnal P . Na druhou stranu, pokud je problém NP-úplný, GI by se rovnal NP a všechny problémy v NP by byly řešitelné v kvazi-polynomickém čase.

Jak je běžné pro třídy složitosti v polynomiální časové hierarchii , problém se nazývá GI-hard, pokud dojde k Turingově redukci polynomiálního času z jakéhokoli problému v GI na tento problém, tj. Řešení polynomiálního času na obtížný problém GI by poskytlo polynomiálně časové řešení problému izomorfismu grafu (a tak všech problémů v GI ). Problém se nazývá úplný pro GI , nebo GI-úplný , pokud je jak GI-tvrdý, tak polynomiální časové řešení problému GI by přineslo řešení polynomiálního času . ${\ displaystyle X}$ ${\ displaystyle X}$

Problém izomorfismu grafu je obsažen v NP i co- AM . GI je obsažen v a nízké pro parity P , jakož i obsažené v potenciálně mnohem menší třídy SPP . To, že leží v paritě P, znamená, že problém izomorfismu grafu není o nic těžší než určit, zda má polynomiální časově nedeterministický Turingův stroj sudý nebo lichý počet akceptačních cest. Pro ZPP ^NP je také obsažen a nízký GI . To v podstatě znamená, že účinný algoritmus Las Vegas s přístupem k věštci NP dokáže vyřešit izomorfismus grafů tak snadno, že nezískává žádnou moc díky schopnosti to dělat v konstantním čase.

GI-úplné a GI-těžké problémy

Izomorfismus jiných předmětů

Existuje řada tříd matematických objektů, u nichž je problém isomorfismu problémem úplného GI. Řada z nich jsou grafy vybavené dalšími vlastnostmi nebo omezeními:

digrafy
označené grafy s tím, že pro zachování štítků není vyžadován izomorfismus, ale pouze vztah ekvivalence skládající se z dvojic vrcholů se stejným štítkem
„polarizované grafy“ (vytvořené z úplného grafu K _m a prázdného grafu K _n plus některé hrany spojující dva; jejich izomorfismus musí zachovat přepážku)
2- barevné grafy
výslovně dané konečné struktury
multigrafy
hypergrafy
konečné automaty
Markovské rozhodovací procesy
komutativní třída 3 nilpotentní (tj. xyz = 0 pro každý prvek x , y , z ) poloskupiny
konečná pozice asociativních algeber nad fixním algebraicky uzavřeným polem s nulovým čtvercovým radikálem a komutativním faktorem nad radikálem.
gramatiky bez kontextu
vyvážené neúplné návrhy bloků
Uznání kombinatorické izomorfismus z konvexních Polytopes reprezentovaných vrchol-fasety výskytu.

Kompletní GI třídy grafů

Třída grafů se nazývá GI-Complete, pokud je rozpoznání izomorfismu pro grafy z této podtřídy problémem GI-Complete. Následující třídy jsou úplné GI:

propojené grafy
grafy průměru 2 a poloměru 1
řízené acyklické grafy
pravidelné grafy
bipartitní grafy bez netriviálních silně pravidelných podgrafů
bipartitní eulerovské grafy
bipartitní pravidelné grafy
čárové grafy
rozdělené grafy
akordální grafy
pravidelné komplementární grafy
polytopní grafy obecných, jednoduchých a zjednodušujících konvexních polytopů v libovolných rozměrech.

Mnoho tříd digrafů je také úplných GI.

Další problémy s úplným GI

Kromě problémů s izomorfismem existují i další netriviální problémy úplné GI.

Rozpoznání vlastní komplementarity grafu nebo digrafu.
Problém klika pro třídu tzv M -graphs. Je ukázáno, že nalezení izomorfismu pro n -vrcholné grafy je ekvivalentní nalezení n -kliky v M -grafu velikosti n ² . Tato skutečnost je zajímavá, protože problém nalezení ( n - ε ) -kliky v M- grafu velikosti n ² je NP-úplný pro libovolně malá kladná ε.
Problém homeomorfismu 2-komplexů.

GI-těžké problémy

Problém počítání počtu izomorfismů mezi dvěma grafy je polynomiálně časově ekvivalentní problému s určením, zda existuje i jeden.
Problém rozhodování, zda dva konvexní polytopy dané V-popisem nebo H-popisem jsou projektivně nebo afinitně izomorfní. Ta druhá znamená existenci projektivní nebo afinní mapy mezi prostory, které obsahují dva polytopy (ne nutně stejné dimenze), což vyvolává bijekci mezi polytopy.

Kontrola programu

Manuel Blum a Sampath Kannan ( 1995 ) ukázali pravděpodobnostní kontrolu programů pro grafový izomorfismus. Předpokládejme, že P je nárokovaný polynomiální časový postup, který kontroluje, zda jsou dva grafy izomorfní, ale není důvěryhodný. Chcete -li zkontrolovat, zda jsou G a H izomorfní:

Zeptejte se P, zda G a H jsou izomorfní.
- Pokud odpovíte „ano“:
  - Pokus o konstrukci izomorfismu pomocí P jako podprogramu. Označte vrchol u v G a v v H a upravte grafy tak, aby byly výrazné (s malou místní změnou). Zeptejte se P, zda jsou upravené grafy izomorfní. Pokud ne, změňte v na jiný vrchol. Pokračujte v hledání.
  - Buď bude izomorfismus nalezen (a může být ověřen), nebo P bude sám sobě odporovat.
- Pokud odpovíte „ne“:
  - Proveďte následujících 100krát. Vyberte náhodně G nebo H a náhodně permutujte jeho vrcholy. Zadat P v případě, že graf je izomorfní G a H . (Stejně jako v AM protokolu pro graf nonisomorphism).
  - Pokud některý z testů neuspěje, posuďte P jako neplatný program. V opačném případě odpovězte „ne“.

Tento postup je polynomiální a dává správnou odpověď, pokud P je správný program pro izomorfismus grafů. Jestliže P není správný program, ale odpoví správně na G a H , bude kontrola buď dát správnou odpověď, nebo zjišťovat neplatnou chování P . Pokud P není správný program a odpoví nesprávně na G a H , kontroler detekuje neplatné chování P s vysokou pravděpodobností nebo odpoví špatně s pravděpodobností 2 ⁻¹⁰⁰ .

Je pozoruhodné, že P se používá pouze jako blackbox.

Aplikace

Grafy se běžně používají ke kódování strukturálních informací v mnoha oblastech, včetně počítačového vidění a rozpoznávání vzorů , a přizpůsobování grafů , tj. Identifikace podobností mezi grafy, je v těchto oblastech důležitým nástrojem. V těchto oblastech je problém izomorfismu grafu známý jako přesné přizpůsobení grafu.

V cheminformatice a v matematické chemii se k identifikaci chemické sloučeniny v chemické databázi používá testování grafového izomorfismu . Také v organické matematické chemii je testování izomorfismu užitečné pro generování molekulárních grafů a pro počítačovou syntézu .

Chemické vyhledávání v databázi je příkladem dolování grafických dat , kde se často používá přístup kanonizace grafů . Zejména řada identifikátorů pro chemické látky , jako jsou SMILES a InChI , navržené tak, aby poskytovaly standardní a pro člověka čitelné způsoby kódování molekulárních informací a usnadňovaly vyhledávání takových informací v databázích a na webu, použijte kanonizační krok v jejich výpočet, což je v podstatě kanonizace grafu, který představuje molekulu.

V automatizaci elektronického designu je izomorfismus základem kroku návrhu obvodu Layout Versus Schematic (LVS), což je ověření, zda jsou elektrické obvody reprezentované schématem zapojení a rozložením integrovaného obvodu stejné.

Viz také

Poznámky

Reference

Aho, Alfred V .; Hopcroft, John ; Ullman, Jeffrey D. (1974), The Design and Analysis of Computer Algorithms , Reading, MA: Addison-Wesley.
Arvind, Vikraman; Köbler, Johannes (2000), „Graph isomorphism is low for ZPP (NP) and other lowness results.“, Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science , Lecture Notes in Computer Science , 1770 , Springer-Verlag, pp . 431–442 , doi : 10,1007/3-540-46541-3_36 , ISBN 3-540-67141-2, MR 1781752.
Arvind, Vikraman; Kurur, Piyush P. (2006), „Graph isomorphism is in SPP“, Information and Computation , 204 (5): 835–852, doi : 10.1016/j.ic.2006.02.002 , MR 2226371.
Babai, László (1980), „O složitosti kanonického značení silně pravidelných grafů“, SIAM Journal on Computing , 9 (1): 212–216, doi : 10,1137/0209018 , MR 0557839.
Babai, László ; Codenotti, Paolo (2008), „Izomorfismus hypergrafů nízké hodnosti v mírně exponenciálním čase“ (PDF) , Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008) , IEEE Computer Society, pp. 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), „Isomorphism of graphs with bounded eigenvalue multiplicity“, Proceedings of the 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), „Výpočetní složitost a klasifikace konečných jednoduchých skupin“, Proceedings of the 24th Annual Symposium on Foundations of Computer Science (FOCS) , pp. 162–171, doi : 10.1109/SFCS.1983.10 , S2CID 6670135.
Babai, László ; Luks, Eugene M. (1983), „Canonical labeling of graphs“, Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC '83) , str. 171–183, doi : 10.1145/800061.808746 , ISBN 0-89791-099-0, S2CID 12572142.
Babai, László (2015), Graph Isomorphism in Quasipolynomial Time , arXiv : 1512.03547 , Bibcode : 2015arXiv151203547B
Baird, HS; Cho, YE (1975), „Systém ověřování návrhu uměleckých děl“ , Proceedings of the 12th Design Automation Conference (DAC '75) , Piscataway, NJ, USA: IEEE Press, s. 414–420.
Blum, Manuel ; Kannan, Sampath (1995), „Designing programs that check their work“ , Journal of the ACM , 42 (1): 269–291, CiteSeerX 10.1.1.38.2537 , doi : 10.1145/200836.200880 , S2CID 52151779.
Bodlaender, Hans (1990), „Polynomiální algoritmy pro grafový izomorfismus a chromatický index na dílčích k- stromech“, Journal of Algorithms , 11 (4): 631–643, doi : 10,1016/0196-6774 (90) 90013-5 , MR 1079454.
Booth, Kellogg S .; Colbourn, CJ (1977), Problémy polynomiálně ekvivalentní izomorfismu grafů , Technická zpráva, CS-77-04, Katedra informatiky, University of Waterloo.
Booth, Kellogg S .; Lueker, George S. (1979), „Lineární časový algoritmus pro rozhodování o intervalu izomorfismu grafu“ , Journal of the ACM , 26 (2): 183–195, doi : 10.1145/322123.322125 , MR 0528025 , S2CID 18859101.
Boucher, C .; Loker, D. (2006), Úplnost izomorfismu grafu pro dokonalé grafy a podtřídy dokonalých grafů (PDF) , Technická zpráva, CS-2006-32, Katedra informatiky, University of Waterloo.
Chung, Fan RK (1985), „O šířce řezu a topologické šířce pásma stromu“, SIAM Journal o algebraických a diskrétních metodách , 6 (2): 268–277, doi : 10,1137/0606026 , MR 0778007.
Colbourn, CJ (1981), „O testování izomorfismu permutačních grafů“, Networks , 11 : 13–21, doi : 10,1002/net.3230110103 , MR 0608916.
Colbourn, Marlene Jones; Colbourn, Charles J. (1978), „Graph isomorphism and self -plementar graphs“, ACM SIGACT News , 10 (1): 25–29, doi : 10.1145/1008605.1008608 , S2CID 35157300.
Cook, Diane J .; Holder, Lawrence B. (2007), „Section 6.2.1: Canonical Labelling“ , Mining Graph Data , Wiley, s. 120–122, ISBN 978-0-470-07303-2.
Datta, S .; Limaye, N .; Nimbhorkar, P .; Thierauf, T .; Wagner, F. (2009), „Izomorfismus planárních grafů je v log-prostoru“, 24. 24. výroční konference IEEE o výpočetní složitosti , 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), „Polynomiálně-časový algoritmus pro určování izomorfismu grafů fixního rodu“, Proceedings of the 12th Annual ACM Symposium on Theory of Computing , pp. 236–243, doi : 10,1145/800141.804671 , ISBN 0-89791-017-6, S2CID 16345164.
Foggia, P .; Sansone, C .; Vento, M. (2001), „Srovnání výkonu pěti algoritmů pro grafový izomorfismus“ (PDF) , Proc. 3. IAPR-TC15 Workshop Grafické reprezentace v rozpoznávání vzorů , s. 188–199.
Garey, Michael R .; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , WH Freeman, ISBN 978-0-7167-1045-5.
Grigor'ev, D. Ju. (1981), „Složitost„ divokých “maticových problémů a izomorfismu algeber a grafů“, Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta Imeni VA Steklova Akademii Nauk SSSR (LOMI) (v ruštině), 105 : 10–17, 198 , MR 0628981. Anglický překlad v Journal of Mathematical Sciences 22 (3): 1285–1289, 1983.
Hopcroft, John ; Wong, J. (1974), „Lineární časový algoritmus pro izomorfismus rovinných grafů“, 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: Filtrování databází grafů pomocí strojového učení , Dissertationen zur künstlichen Intelligenz, 293 , AKA, ISBN 1-58603-557-6.
Kaibel, Volker; Schwartz, Alexander (2003), „O složitosti problémů polytopního izomorfismu“ , Graphs and Combinatorics , 19 (2): 215–230, arXiv : math/0106093 , doi : 10,1007/s00373-002-0503-y , MR 1996205 , S2CID 179936 , archivováno od originálu dne 2015-07-21.
Kelly, Paul J. (1957), „A congruence theorem for trees“, Pacific Journal of Mathematics , 7 : 961–968, doi : 10,2140/pjm.1957.7.961 , MR 0087949.
Köbler, Johannes; Schöning, Uwe ; Torán, Jacobo (1992), „Graph isomorphism is low for PP“, Computational Complexity , 2 (4): 301–330, doi : 10.1007/BF01200427 , MR 1215315 , S2CID 8542603.
Kozen, Dexter (1978), „A clique problem equivalent to graph isomorphism“, ACM SIGACT News , 10 (2): 50–52, doi : 10.1145/990524.990529 , S2CID 52835766.
Luks, Eugene M. (1982), „Izomorfismus grafů ohraničené valence lze testovat v polynomiálním čase“, Journal of Computer and System Sciences , 25 : 42–65, doi : 10,1016/0022-0000 (82) 90009-5 , MR 0685360 , S2CID 2572728.
Luks, Eugene M. (1986), "Paralelní algoritmy pro permutační skupiny a grafový izomorfismus", Proč. IEEE Symp. Foundations of Computer Science , s. 292–302.
Mathon, Rudolf (1979), „Poznámka k problému s počítáním izomorfismu grafu“, Letters Processing Letters , 8 (3): 131–132, doi : 10.1016/0020-0190 (79) 90004-8 , MR 0526453.
McKay, Brendan D. (1981), „Praktický grafový izomorfismus“ , 10. místo. Manitobská konference o numerické matematice a výpočetní technice (Winnipeg, 1980) , Congressus Numerantium, 30 , s. 45–87, MR 0635936.
Miller, Gary (1980), „Testování izomorfismu pro grafy ohraničeného rodu“, Proceedings of the 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), „Testování izomorfismu a kanonické formy pro k -smrtelné grafy (zobecnění ohraničené valence a ohraničeného rodu)“, Proc. Int. Konf. on Foundations of Computer Theory , Lecture Notes in Computer Science , 158 , pp. 310–327, doi : 10.1007/3-540-12689-9_114. Celý článek v Informacích a kontrole 56 (1–2): 1–20, 1983.
Moore, Cristopher ; Russell, Alexander; Schulman, Leonard J. (2008), „Symetrická skupina vzdoruje silnému Fourierovu vzorkování“, SIAM Journal on Computing , 37 (6): 1842–1864, arXiv : quant-ph/0501056 , doi : 10,1137/050644896 , MR 2386215.
Muzychuk, Michail (2004), „Řešení problému isomorfismu pro oběžné grafy“, Proc. Londýnská matematika. Soc. , 88 : 1–41, doi : 10,1112/s0024611503014412 , MR 2018956.
Narayanamurthy, SM; Ravindran, B. (2008), „O tvrdosti hledání symetrií v Markovových rozhodovacích procesech“ (PDF) , Sborník z dvacáté páté mezinárodní konference o strojovém učení (ICML 2008) , s. 688–696.
Schmidt, Douglas C .; Druffel, Larry E. (1976), „Rychlý algoritmus zpětného sledování k testování směrovaných grafů pro izomorfismus pomocí distančních matic“, Journal of the ACM , 23 (3): 433–445, doi : 10.1145/321958.321963 , MR 0411230 , S2CID 6163956.
Schöning, Uwe (1987), „Grafický izomorfismus je v nízké hierarchii“, sborník ze 4. ročníku sympozia o teoretických aspektech informatiky , s. 114–124; také Journal of Computer and System Sciences 37 : 312–323, 1988.
Shawe-Taylor, John; Pisanski, Tomaž (1994), „Homeomorphism of 2-complexes is graph isomorphism complete“, SIAM Journal on Computing , 23 (1): 120–132, doi : 10.1137/S0097539791198900 , MR 1258998.
Spielman, Daniel A. (1996), „Rychlejší testování izomorfismu silně pravidelných grafů“, Proceedings of the Twenty-osmý ročník ACM Symposium on Theory of Computing (STOC '96) , ACM, s. 576–584, ISBN 978-0-89791-785-8.
Ullman, Julian R. (1976), „Algoritmus pro podgrafický izomorfismus“ (PDF) , Journal of the ACM , 23 : 31–42 , CiteSeerX 10.1.1.361.7741 , doi : 10.1145/321921.321925 , MR 0495173 , S2CID 17268751.

Průzkumy a monografie

Přečtěte si, Ronald C .; Corneil, Derek G. (1977), „The graph isomorphism disease“, Journal of Graph Theory , 1 (4): 339–363, doi : 10,1002/jgt.3190010410 , MR 0485586.
Gati, G. (1979), „Další anotovaná bibliografie o nemoci izomorfismu“, Journal of Graph Theory , 3 (2): 95–109, doi : 10,1002/jgt.3190030202.
Zemlyachenko, VN; Korneenko, NM; Tyshkevich, RI (1985), „Graph isomorphism problem“, Journal of Mathematical Sciences , 29 (4): 1426–1481, doi : 10.1007/BF02104746 , S2CID 121818465. (Přeloženo ze Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. VA Steklova AN SSSR (Záznamy seminářů Leningradského oddělení Steklovova matematického ústavu Akademie věd SSSR ), sv. 118, s. 83–158, 1982.)
Arvind, V .; Torán, Jacobo (2005), „Testování izomorfismu: Perspektivy a otevřené problémy“ (PDF) , Bulletin Evropské asociace pro teoretickou informatiku , 86 : 66–84. (Krátký průzkum otevřených otázek souvisejících s problémem izomorfismu u grafů, prstenů a skupin.)
Köbler, Johannes; Schöning, Uwe ; Torán, Jacobo (1993), The Graph Isomorphism Problem: its Structural Complexity , Birkhäuser, ISBN 978-0-8176-3680-7. ( Z přebalu knihy: Knihy se zaměřují na problematiku výpočetní složitosti problému a představují několik nedávných výsledků, které poskytují lepší pochopení relativní polohy problému ve třídě NP i v jiných třídách složitosti.)
Johnson, David S. (2005), „Sloupec NP-úplnost“, ACM Transactions on Algorithms , 1 (1): 160–176, doi : 10,1145/1077464.1077476 , S2CID 12604799. (Toto 24. vydání Sloupku pojednává o současném stavu otevřených problémů z knihy Počítače a neotřesitelnost a předchozích sloupců, zejména z grafického izomorfismu.)
Torán, Jacobo; Wagner, Fabian (2009), „The complexity of planar graph isomorphism“ (PDF) , Bulletin of the European Association for Theoretical Computer Science , 97 , archived from the original (PDF) on 2010-09-20 , retrieved 2010-06- 03.

Software

Grafový izomorfismus , přehled implementací, úložiště algoritmů Stony Brook .

Languages

In other projects