¿Se puede resolver el problema del isomorfismo de la gráfica en tiempo polinomial?
El problema del isomorfismo de grafos es el problema computacional de determinar si dos grafos finitos son isomorfos .
No se sabe que el problema se pueda resolver en tiempo polinomial ni que sea NP-completo y, por lo tanto, puede estar en la clase de complejidad computacional NP-intermedia . Se sabe que el problema del isomorfismo del grafo se encuentra en la jerarquía baja de la clase NP , lo que implica que no es NP-completo a menos que la jerarquía de tiempo polinomial colapse a su segundo nivel. [1] Al mismo tiempo, el isomorfismo de muchas clases especiales de gráficos se puede resolver en tiempo polinomial y, en la práctica, el isomorfismo de gráficos a menudo se puede resolver de manera eficiente. [2]
Este problema es un caso especial del problema de isomorfismo de subgrafo , [3] que pregunta si un grafo G dado contiene un subgrafo que es isomorfo a otro grafo H dado ; se sabe que este problema es NP-completo. También se sabe que es un caso especial del problema del subgrupo oculto no abeliano sobre el grupo simétrico . [4]
En el área del reconocimiento de imágenes , se conoce como coincidencia exacta de gráficos . [5]
Lo último
En noviembre de 2015, Babai anunció un algoritmo de tiempo cuasipolinomial para todos los gráficos, es decir, uno con tiempo de ejecución para algunos arreglados . [6] [7] [8] [9] El 4 de enero de 2017, Babai se retractó de la afirmación cuasi-polinomial y declaró un límite de tiempo sub-exponencial en su lugar después de que Harald Helfgott descubrió una falla en la prueba. El 9 de enero de 2017, Babai anunció una corrección (publicada en su totalidad el 19 de enero) y restauró la afirmación cuasi-polinomial, con Helfgott confirmando la corrección. [10] [11] Helfgott afirma además que se puede tomar c = 3 , por lo que el tiempo de ejecución es 2 O ((log n ) 3 ) . [12] [13]
Antes de esto, el mejor algoritmo teórico actualmente aceptado se debió a Babai & Luks (1983) , y se basa en el trabajo anterior de Luks (1982) combinado con un algoritmo subfactorial de VN Zemlyachenko ( Zemlyachenko, Korneenko & Tyshkevich 1985 ). El algoritmo tiene un tiempo de ejecución 2 O ( √ n log n ) para gráficos con n vértices y se basa en la clasificación de grupos simples finitos . Sin este teorema de clasificación, un poco más débil unido 2 O ( √ n log 2 n ) se obtuvo primero para gráficos fuertemente regulares por László Babai ( 1980 ), y luego se extendió a gráficos generales por Babai y Luks (1983) . La mejora del exponente √ n es un gran problema abierto; para gráficos fuertemente regulares, esto fue hecho por Spielman (1996) . Para los hipergráficos de rango acotado, Babai y Codenotti (2008) obtuvieron un límite superior subexponencial que coincide con el caso de los gráficos .
Hay varios algoritmos prácticos en competencia para el isomorfismo de grafos, como los de McKay (1981) , Schmidt y Druffel (1976) y Ullman (1976) . Si bien parecen funcionar bien en gráficos aleatorios , un inconveniente importante de estos algoritmos es su rendimiento de tiempo exponencial en el peor de los casos . [14]
El problema de isomorfismo de grafo es computacionalmente equivalente al problema de calcular el grupo de automorfismo de un grafo, [15] [16] y es más débil que el problema de isomorfismo de grupo de permutación y el problema de intersección de grupo de permutación. Para los dos últimos problemas, Babai, Kantor y Luks (1983) obtuvieron límites de complejidad similares a los del isomorfismo de grafos.
Casos especiales resueltos
Varios casos especiales importantes del problema de isomorfismo de grafos tienen soluciones eficientes en tiempo polinomial:
- Árboles [17] [18]
- Gráficas planas [19] (De hecho, el isomorfismo de las gráficas planas está en el espacio logarítmico , [20] una clase contenida en P )
- Gráficos de intervalos [21]
- Gráficos de permutación [22]
- Gráficos circulantes [23]
- Gráficos de parámetros acotados
- Gráficos de ancho de árbol acotado [24]
- Gráficas de género acotado [25] (Las gráficas planas son gráficas del género 0.)
- Gráficos de grado acotado [26]
- Gráficos con multiplicidad de valores propios acotada [27]
- k -Gráficos contráctiles (una generalización de grado acotado y género acotado) [28]
- El isomorfismo que conserva el color de los gráficos coloreados con multiplicidad de color limitada (es decir, como máximo k vértices tienen el mismo color para un k fijo ) está en la clase NC , que es una subclase de P [29]
Clase de complejidad GI
Dado que no se sabe que el problema del isomorfismo del grafo sea NP-completo ni se sepa que sea manejable, los investigadores han tratado de comprender mejor el problema definiendo una nueva clase GI , el conjunto de problemas con una reducción de Turing en tiempo polinomial al isomorfismo del grafo. problema. [30] Si, de hecho, el problema gráfico isomorfismo es resoluble en tiempo polinómico, GI sería igual a P . Por otro lado, si el problema es NP-completo, GI sería igual a NP y todos los problemas en NP podrían resolverse en un tiempo cuasi-polinómico.
Como es común para las clases de complejidad dentro de la jerarquía de tiempo polinomial , un problema se llama GI-hard si hay una reducción de Turing en tiempo polinomial de cualquier problema en GI a ese problema, es decir, una solución en tiempo polinomial para un problema GI-hard daría una solución de tiempo polinomial al problema de isomorfismo de la gráfica (y así todos los problemas en GI ). Un problemase llama completo para GI , o GI-completo , si es GI-hard y una solución en tiempo polinomial para el problema GI produciría una solución en tiempo polinomial para.
El problema del isomorfismo gráfico está contenido tanto en NP como en co- AM . GI está contenido y es bajo para la paridad P , así como también está contenido en la clase SPP potencialmente mucho más pequeña . [31] El hecho de que se encuentre en la paridad P significa que el problema del isomorfismo del grafo no es más difícil que determinar si una máquina de Turing no determinista en tiempo polinomial tiene un número par o impar de caminos de aceptación. GI también está contenido y es bajo para ZPP NP . [32] Esto esencialmente significa que un algoritmo eficiente de Las Vegas con acceso a un oráculo NP puede resolver el isomorfismo de grafos con tanta facilidad que no obtiene ningún poder al tener la capacidad de hacerlo en tiempo constante.
Problemas GI-completo y GI-hard
Isomorfismo de otros objetos
Hay una serie de clases de objetos matemáticos para los que el problema del isomorfismo es un problema completo de IG. Algunos de ellos son gráficos dotados de propiedades o restricciones adicionales: [33]
- dígrafos [33]
- gráficos etiquetados , con la condición de que no se requiere un isomorfismo para preservar las etiquetas, [33] sino solo la relación de equivalencia que consiste en pares de vértices con la misma etiqueta
- "gráficos polarizados" (hechos de un gráfico completo K m y un gráfico vacío K n más algunos bordes que conectan los dos; su isomorfismo debe preservar la partición) [33]
- Gráficos de 2 colores [33]
- estructuras finitas dadas explícitamente [33]
- multigraphs [33]
- hipergrafos [33]
- autómatas finitos [33]
- Procesos de decisión de Markov [34]
- clase conmutativa 3 nilpotente (es decir, xyz = 0 para todos los elementos x , y , z ) semigrupos [33]
- álgebras asociativas de rango finito sobre un campo fijo algebraicamente cerrado con radical al cuadrado cero y factor conmutativo sobre el radical. [33] [35]
- gramáticas libres de contexto [33]
- diseños de bloques incompletos equilibrados [33]
- Reconocimiento del isomorfismo combinatorio de politopos convexos representados por incidencias vértice-faceta. [36]
Clases de gráficos GI-complete
Una clase de gráficos se llama GI-completo si el reconocimiento del isomorfismo para los gráficos de esta subclase es un problema GI-completo. Las siguientes clases tienen IG completa: [33]
- gráficos conectados [33]
- gráficos de diámetro 2 y radio 1 [33]
- gráficos acíclicos dirigidos [33]
- gráficos regulares [33]
- gráficos bipartitos sin subgrafos no triviales fuertemente regulares [33]
- gráficos eulerianos bipartitos [33]
- gráficos regulares bipartitos [33]
- gráficos de líneas [33]
- gráficos divididos [37]
- grafos de cuerdas [33]
- gráficos autocomplementarios regulares [33]
- grafos politopales de politopos convexos generales, simples y simpliciales en dimensiones arbitrarias. [38]
Muchas clases de dígrafos también son GI-completos.
Otros problemas gastrointestinales completos
Hay otros problemas gastrointestinales completos no triviales además de los problemas de isomorfismo.
- El reconocimiento de la autocomplementariedad de un gráfico o dígrafo. [39]
- Un problema de camarilla para una clase de los llamados gráficos - M . Se muestra que encontrar un isomorfismo para n gráficos de vértices es equivalente a encontrar un n- clique en un gráfico M de tamaño n 2 . Este hecho es interesante porque el problema de encontrar un círculo ( n - ε ) en una gráfica M de tamaño n 2 es NP-completo para ε positivos arbitrariamente pequeños. [40]
- El problema del homeomorfismo de 2 complejos. [41]
Problemas gastrointestinales difíciles
- El problema de contar el número de isomorfismos entre dos gráficas es equivalente en tiempo polinomial al problema de decir si existe uno solo. [42]
- El problema de decidir si dos politopos convexos dados por la descripción V o la descripción H son proyectiva o afinamente isomórficos. Esto último significa la existencia de un mapa proyectivo o afín entre los espacios que contienen los dos politopos (no necesariamente de la misma dimensión) que induce una biyección entre los politopos. [38]
Comprobación del programa
Manuel Blum y Sampath Kannan ( 1995 ) han mostrado un verificador probabilístico para programas de isomorfismo de grafos. Suponga que P es un procedimiento de tiempo polinomial que verifica si dos gráficos son isomórficos, pero no es de confianza. Para comprobar si G y H son isomorfos:
- Pregunte a P si G y H son isomorfos.
- Si la respuesta es sí":
- Intente construir un isomorfismo usando P como subrutina. Marque un vértice u en G y v en H , y modifique las gráficas para hacerlas distintivas (con un pequeño cambio local). Pregunte a P si las gráficas modificadas son isomorfas. Si no, cambie v a un vértice diferente. Continuar buscando.
- O se encontrará el isomorfismo (y se puede verificar), o P se contradecirá.
- Si la respuesta es "no":
- Realice las siguientes 100 veces. Elija aleatoriamente G o H , y permute aleatoriamente sus vértices. Pregunta P si el gráfico es isomorfo a G y H . (Como en el protocolo AM para el nonisomorfismo gráfico).
- Si falla alguna de las pruebas, juzgue P como programa no válido. De lo contrario, responda "no".
- Si la respuesta es sí":
Este procedimiento es de tiempo polinomial y da la respuesta correcta si P es un programa correcto para el isomorfismo de grafos. Si P no es un programa correcto, pero responde correctamente en G y H , el corrector o bien dar la respuesta correcta, o detectar comportamientos no válido de P . Si P no es un programa correcto y responde incorrectamente en G y H , el verificador detectará un comportamiento no válido de P con alta probabilidad, o responderá incorrectamente con probabilidad 2 −100 .
En particular, P se usa solo como caja negra.
Aplicaciones
Los gráficos se utilizan comúnmente para codificar información estructural en muchos campos, incluida la visión por computadora y el reconocimiento de patrones , y la coincidencia de gráficos , es decir, la identificación de similitudes entre gráficos, es una herramienta importante en estas áreas. En estas áreas, el problema de isomorfismo gráfico se conoce como coincidencia gráfica exacta. [43]
En cheminformatics y en química matemática , pruebas gráfico isomorfismo se utiliza para identificar un compuesto químico dentro de una base de datos químicos . [44] Además, en química orgánica matemática, las pruebas de isomorfismo de gráficos son útiles para la generación de gráficos moleculares y para la síntesis por computadora .
La búsqueda de bases de datos químicas es un ejemplo de minería de datos gráficos , donde a menudo se utiliza el enfoque de canonización de gráficos . [45] En particular, varios identificadores de sustancias químicas , como SMILES e InChI , diseñados para proporcionar una forma estándar y legible por humanos de codificar información molecular y facilitar la búsqueda de dicha información en bases de datos y en la web, utilizan paso de canonización en su cálculo, que es esencialmente la canonización del gráfico que representa la molécula.
En la automatización del diseño electrónico, el isomorfismo gráfico es la base del paso de diseño del circuito Layout Versus Schematic (LVS), que es una verificación de si los circuitos eléctricos representados por un esquema de circuito y un diseño de circuito integrado son iguales. [46]
Ver también
- Problema de automorfismo gráfico
- Canonización de grafos
Notas
- ^ Schöning (1987) .
- ^ McKay (1981) .
- ^ Ullman (1976) .
- ^ Moore, Russell y Schulman (2008) .
- ^ Endika Bengoetxea, "Coincidencia de gráficos inexactos mediante la estimación de algoritmos de distribución" , Ph. D., 2002, Capítulo 2: El problema de coincidencia de gráficos (consultado el 28 de junio de 2017)
- ^ "El matemático afirma un gran avance en la teoría de la complejidad" . Ciencia . 10 de noviembre de 2015.
- ↑ Babai (2015)
- ^ Video de la primera conferencia de 2015 vinculado desde la página de inicio de Babai
- ^ "El problema del isomorfismo gráfico" . Comunicaciones de la ACM . Consultado el 4 de mayo de 2021 .
- ^ Babai, László (9 de enero de 2017), Actualización de isomorfismo gráfico
- ^ Erica Klarreich , Graph Isomorphism Vanquished - Again , Quanta Magazine, 14 de enero de 2017, ver aquí
- ^ Helfgott, Harald (16 de enero de 2017), Isomorphismes de graphes en temps cuasi-polyinomial (d'après Babai et Luks, Weisfeiler-Leman ...) , arXiv : 1701.04372 , Bibcode : 2017arXiv170104372A
- ^ Dona, Daniele; Bajpai, Jitendra; Helfgott, Harald Andrés (12 de octubre de 2017). "Graficar isomorfismos en tiempo cuasi-polinomial". arXiv : 1710.04574 [ math.GR ].
- ^ Foggia, Sansone y Vento (2001) .
- ^ Luks, Eugene (1 de septiembre de 1993). "Grupos de permutación y cálculo de tiempo polinomial". Serie DIMACS en Matemática Discreta e Informática Teórica . 11 . Providence, Rhode Island: Sociedad Matemática Estadounidense. págs. 139-175. doi : 10.1090 / dimacs / 011/11 . ISBN 978-0-8218-6599-6. ISSN 1052-1798 .
- ^ Algeboy ( https://cs.stackexchange.com/users/90177/algeboy ), Graph isomorphism and the automorphism group, URL (versión: 2018-09-20): https://cs.stackexchange.com/q/ 97575
- ^ Kelly (1957) .
- ^ Aho, Hopcroft y Ullman (1974) , p. 84-86.
- ^ Hopcroft y Wong (1974) .
- ^ Datta y col. (2009) .
- ^ Booth y Lueker (1979) .
- ^ Colbourn (1981) .
- ^ Muzychuk (2004) .
- ^ Bodlaender (1990) .
- ^ Miller 1980 ; Filotti y Mayer 1980 .
- ^ Luks (1982) .
- ^ Babai, Grigoryev y Mount (1982) .
- ^ Miller (1983) .
- ^ Luks (1986) .
- ^ Booth y Colbourn 1977 ; Köbler, Schöning y Torán 1993 .
- ^ Köbler, Schöning y Torán 1992 ; Arvind y Kurur 2006
- ^ Arvind y Köbler (2000) .
- ^ a b c d e f g h i j k l m n o p q r s t u v w x Zemlyachenko, Korneenko y Tyshkevich (1985)
- ^ Narayanamurthy y Ravindran (2008) .
- ^ Grigor'ev (1981) .
- ^ Johnson (2005) ; Kaibel y Schwartz (2003) .
- ^ Chung (1985) .
- ↑ a b Kaibel y Schwartz (2003) .
- ^ Colbourn y Colbourn (1978) .
- ^ Kozen (1978) .
- ^ Shawe-Taylor y Pisanski (1994) .
- ^ Mathon (1979) ; Johnson 2005 .
- ^ Endika Bengoetxea, Ph.D., Resumen
- ^ Irniger (2005) .
- ^ Cocinero y titular (2007) .
- ^ Baird y Cho (1975) .
Referencias
- Aho, Alfred V .; Hopcroft, John ; Ullman, Jeffrey D. (1974), El diseño y análisis de algoritmos informáticos , Reading, MA: Addison-Wesley.
- Arvind, Vikraman; Köbler, Johannes (2000), "Graph isomorphism is low for ZPP (NP) and other lowness results.", Actas del 17º Simposio anual sobre aspectos teóricos de la informática , Lecture Notes in Computer Science , 1770 , Springer-Verlag, págs. . 431–442 , doi : 10.1007 / 3-540-46541-3_36 , ISBN 3-540-67141-2, Señor 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), "Sobre la complejidad del etiquetado canónico de gráficos fuertemente regulares", SIAM Journal on Computing , 9 (1): 212-216, doi : 10.1137 / 0209018 , MR 0557839.
- Babai, László ; Codenotti, Paolo (2008), "Isomorfismo de hipergrafías de rango bajo en tiempo moderadamente exponencial" (PDF) , Actas del 49º Simposio Anual de IEEE sobre Fundamentos de la Ciencia de la Computación (FOCS 2008) , IEEE Computer Society, págs. 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), "Isomorfismo de gráficos con multiplicidad de valor propio acotado", Actas del 14 ° Simposio anual de ACM sobre teoría de la computación , págs. 310-324, doi : 10.1145 / 800070.802206 , ISBN 0-89791-070-2, S2CID 12837287.
- Babai, László ; Kantor, William ; Luks, Eugene (1983), "La complejidad computacional y la clasificación de grupos finitos simples", Actas del 24 ° Simposio anual sobre fundamentos de la informática (FOCS) , págs. 162-171, doi : 10.1109 / SFCS.1983.10 , S2CID 6670135.
- Babai, László ; Luks, Eugene M. (1983), "Canonical labeling of graphs", Actas del Decimoquinto Simposio Anual de ACM sobre Teoría de la Computación (STOC '83) , págs. 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), "Un sistema de verificación del diseño de obras de arte" , Actas de la 12ª Conferencia de Automatización del Diseño (DAC '75) , Piscataway, Nueva Jersey, EE. UU.: IEEE Press, págs. 414–420.
- Blum, Manuel ; Kannan, Sampath (1995), "Diseñar programas que controlan su trabajo" , Journal of the ACM , 42 (1): 269–291, CiteSeerX 10.1.1.38.2537 , doi : 10.1145 / 200836.200880 , S2CID 52151779.
- Bodlaender, Hans (1990), "Algoritmos polinomiales para isomorfismo de grafos e índice cromático en árboles k parciales", Journal of Algorithms , 11 (4): 631–643, doi : 10.1016 / 0196-6774 (90) 90013-5 , Señor 1079454.
- Booth, Kellogg S .; Colbourn, CJ (1977), Problemas polinomialmente equivalentes al isomorfismo gráfico , Informe técnico, CS-77-04, Departamento de Ciencias de la Computación, Universidad de Waterloo.
- Booth, Kellogg S .; Lueker, George S. (1979), "Un algoritmo de tiempo lineal para decidir el isomorfismo de gráfico de intervalo" , Journal of the ACM , 26 (2): 183-195, doi : 10.1145 / 322123.322125 , MR 0528025 , S2CID 18859101.
- Boucher, C .; Loker, D. (2006), Completitud del isomorfismo de gráficos para gráficos perfectos y subclases de gráficos perfectos (PDF) , Informe técnico, CS-2006-32, Departamento de Ciencias de la Computación, Universidad de Waterloo.
- Chung, Fan RK (1985), "On the cutwidth and the topological bandwidth of a tree", SIAM Journal on Algebraic and Discrete Methods , 6 (2): 268-277, doi : 10.1137 / 0606026 , MR 0778007.
- Colbourn, CJ (1981), "On testing isomorphism of permutation graphs", Networks , 11 : 13-21, doi : 10.1002 / net.3230110103 , MR 0608916.
- Colbourn, Marlene Jones; Colbourn, Charles J. (1978), "Grafismo isomorfismo y gráficos autocomplementarios", ACM SIGACT News , 10 (1): 25-29, doi : 10.1145 / 1008605.1008608 , S2CID 35157300.
- Cook, Diane J .; Holder, Lawrence B. (2007), "Sección 6.2.1: Etiquetado canónico" , Datos de gráficos de minería , Wiley, págs. 120-122, ISBN 978-0-470-07303-2.
- Datta, S .; Limaye, N .; Nimbhorkar, P .; Thierauf, T .; Wagner, F. (2009), "El isomorfismo de grafos planos está en el espacio logarítmico", 24ª Conferencia Anual del IEEE sobre Complejidad Computacional de 2009 , p. 203, arXiv : 0809.2319 , doi : 10.1109 / CCC.2009.16 , ISBN 978-0-7695-3717-7, S2CID 14836820.
- Filotti, IS; Mayer, Jack N. (1980), "Un algoritmo de tiempo polinomial para determinar el isomorfismo de gráficos de género fijo", Actas del 12º Simposio anual de ACM sobre teoría de la computación , págs. 236–243, doi : 10.1145 / 800141.804671 , ISBN 0-89791-017-6, S2CID 16345164.
- Foggia, P .; Sansone, C .; Vento, M. (2001), "Una comparación de rendimiento de cinco algoritmos para isomorfismo de grafos" (PDF) , Proc. 3er Taller IAPR-TC15 Representaciones basadas en gráficos en el reconocimiento de patrones , págs. 188–199.
- Garey, Michael R .; Johnson, David S. (1979), Computadoras e intratabilidad: una guía para la teoría de NP-Completeness , WH Freeman, ISBN 978-0-7167-1045-5.
- Grigor'ev, D. Ju. (1981), "Complejidad de problemas de matrices 'salvajes' y del isomorfismo de álgebras y gráficos", Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta Imeni VA Steklova Akademii Nauk SSSR (LOMI) (en ruso), 105 : 10-17, 198 , MR 0628981. Traducción al inglés en Journal of Mathematical Sciences 22 (3): 1285-1289, 1983.
- Hopcroft, John ; Wong, J. (1974), "Algoritmo de tiempo lineal para el isomorfismo de gráficos planares", Actas del Sexto Simposio Anual de ACM sobre Teoría de la Computación , págs. 172-184, doi : 10.1145 / 800119.803896 , S2CID 15561884.
- Irniger, Christophe-André Mario (2005), Graph Matching: Filtering Databases of Graphs Using Machine Learning , Dissertationen zur künstlichen Intelligenz, 293 , AKA, ISBN 1-58603-557-6.
- Kaibel, Volker; Schwartz, Alexander (2003), "Sobre la complejidad de los problemas de isomorfismo de politopos" , Graphs and Combinatorics , 19 (2): 215-230, arXiv : math / 0106093 , doi : 10.1007 / s00373-002-0503-y , MR 1996205 , S2CID 179936 , archivado desde el original el 21 de julio de 2015.
- Kelly, Paul J. (1957), "Un teorema de congruencia para árboles", 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), "Un problema de camarilla equivalente al isomorfismo de grafos", ACM SIGACT News , 10 (2): 50–52, doi : 10.1145 / 990524.990529 , S2CID 52835766.
- Luks, Eugene M. (1982), "El isomorfismo de gráficos de valencia limitada se puede probar en tiempo polinomial", 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), "Algoritmos paralelos para grupos de permutación e isomorfismo de grafos", Proc. IEEE Symp. Fundamentos de la informática , págs. 292–302.
- Mathon, Rudolf (1979), "Una nota sobre el problema de conteo de isomorfismos gráficos", Information Processing Letters , 8 (3): 131-132, doi : 10.1016 / 0020-0190 (79) 90004-8 , MR 0526453.
- McKay, Brendan D. (1981), "Isomorfismo gráfico práctico" , décimo. Conferencia de Manitoba sobre Matemáticas Numéricas y Computación (Winnipeg, 1980) , Congressus Numerantium, 30 , págs. 45–87, MR 0635936.
- Miller, Gary (1980), "Pruebas de isomorfismo para gráficos de géneros acotados", Actas del 12º Simposio Anual de ACM sobre Teoría de la Computación , págs. 225-235, doi : 10.1145 / 800141.804670 , ISBN 0-89791-017-6, S2CID 13647304.
- Miller, Gary L. (1983), "Prueba de isomorfismo y formas canónicas para gráficos k -contratables (una generalización de valencia limitada y género limitado)", Proc. En t. Conf. on Foundations of Computer Theory , Lecture Notes in Computer Science , 158 , págs. 310–327, doi : 10.1007 / 3-540-12689-9_114. Documento completo en Information and Control 56 (1–2): 1–20, 1983.
- Moore, Cristopher ; Russell, Alexander; Schulman, Leonard J. (2008), "El grupo simétrico desafía el fuerte muestreo de Fourier", SIAM Journal on Computing , 37 (6): 1842-1864, arXiv : quant-ph / 0501056 , doi : 10.1137 / 050644896 , MR 2386215.
- Muzychuk, Mikhail (2004), "Una solución del problema de isomorfismo para gráficos circulantes", Proc. London Math. Soc. , 88 : 1–41, doi : 10.1112 / s0024611503014412 , MR 2018956.
- Narayanamurthy, SM; Ravindran, B. (2008), "Sobre la dureza de encontrar simetrías en los procesos de decisión de Markov" (PDF) , Actas de la XXV Conferencia Internacional sobre Aprendizaje Automático (ICML 2008) , págs. 688–696.
- Schmidt, Douglas C .; Druffel, Larry E. (1976), "Un algoritmo de retroceso rápido para probar grafos dirigidos para isomorfismo usando matrices de distancia", Journal of the ACM , 23 (3): 433–445, doi : 10.1145 / 321958.321963 , MR 0411230 , S2CID 6163956.
- Schöning, Uwe (1987), "El isomorfismo gráfico está en la jerarquía baja", Actas del 4to Simposio anual sobre aspectos teóricos de la informática , págs. 114-124; también 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), "Pruebas de isomorfismo más rápidas de gráficos fuertemente regulares", Actas del vigésimo octavo simposio anual de ACM sobre teoría de la computación (STOC '96) , ACM, págs. 576–584, ISBN 978-0-89791-785-8.
- Ullman, Julian R. (1976), "Un algoritmo para el isomorfismo de subgrafo" (PDF) , Journal of the ACM , 23 : 31–42, CiteSeerX 10.1.1.361.7741 , doi : 10.1145 / 321921.321925 , MR 0495173 , S2CID 17268751.
Encuestas y monografías
- Leer, Ronald C .; Corneil, Derek G. (1977), "La enfermedad del isomorfismo gráfico", Journal of Graph Theory , 1 (4): 339–363, doi : 10.1002 / jgt.3190010410 , MR 0485586.
- Gati, G. (1979), "Bibliografía adicional comentada sobre la enfermedad del isomorfismo", 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. (Traducido de Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. VA Steklova AN SSSR (Registros de seminarios del Departamento de Leningrado del Instituto Steklov de Matemáticas de la Academia de Ciencias de la URSS ), Vol. 118, págs. 83-158, 1982.)
- Arvind, V .; Torán, Jacobo (2005), "Pruebas de isomorfismo: perspectivas y problemas abiertos" (PDF) , Boletín de la Asociación Europea de Ciencias de la Computación Teórica , 86 : 66–84. (Una breve encuesta de preguntas abiertas relacionadas con el problema del isomorfismo para gráficos, anillos y grupos).
- Köbler, Johannes; Schöning, Uwe ; Torán, Jacobo (1993), El problema del isomorfismo gráfico: su complejidad estructural , Birkhäuser, ISBN 978-0-8176-3680-7. ( De la portada del libro : el libro se centra en el tema de la complejidad computacional del problema y presenta varios resultados recientes que proporcionan una mejor comprensión de la posición relativa del problema en la clase NP así como en otras clases de complejidad).
- Johnson, David S. (2005), "The NP-Completeness Column", ACM Transactions on Algorithms , 1 (1): 160–176, doi : 10.1145 / 1077464.1077476 , S2CID 12604799. (Esta 24a edición de la Columna analiza el estado del arte de los problemas abiertos del libro Computers and Intractability y columnas anteriores, en particular, para Graph Isomorphism.)
- Torán, Jacobo; Wagner, Fabian (2009), "La complejidad del isomorfismo de grafos planos" (PDF) , Boletín de la Asociación Europea de Ciencias de la Computación Teórica , 97 , archivado desde el original (PDF) el 2010-09-20 , consultado el 2010-06- 03.
Software
- Isomorfismo de grafos , revisión de implementaciones, The Stony Brook Algorithm Repository .