{"entities":{"Q1913583":{"pageid":1924325,"ns":120,"title":"Item:Q1913583","lastrevid":71146377,"modified":"2026-04-13T19:47:10Z","type":"item","id":"Q1913583","labels":{"en":{"language":"en","value":"A graph isomorphism algorithm using pseudoinverses"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 881182"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1913583$06D05AC9-9E83-4812-B9FE-26A33424B355","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f152a3c0c62b613074eb84f7d774ec0e2f3e02ca","datavalue":{"value":{"text":"A graph isomorphism algorithm using pseudoinverses","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1913583$CC7E5B61-82B3-4BA7-995A-CE39749E7F35","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6dd3946051440df21254493701128fb828657f8c","datavalue":{"value":"0847.05075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1913583$8F6959FF-F524-4DA6-8D8F-0A7802ED1769","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4725f6ca1f221a217d5c9d0f2248e1642027d59d","datavalue":{"value":"10.1007/BF01740543","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1913583$053E97B5-AF37-4546-8836-CDD4CD944650","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1913583$F553D69F-37F1-49F2-BFF7-C0B2E710F141","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e560271c921b84b65a9b7f0d3fa6830623f8af8b","datavalue":{"value":{"entity-type":"item","numeric-id":188629,"id":"Q188629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1913583$37C8DA5A-6C9F-459C-AF01-FEF6EFE75D7D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"40eacd21a7efb3a2fa818fc0823bb429dea7c652","datavalue":{"value":{"time":"+1996-09-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1913583$D8BCF023-A2B8-4791-A046-444EF5865751","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a8e1940fe22030c427f48b6d4f2e2b84c03f2815","datavalue":{"value":"This paper presents a heuristic algorithm of complexity at most \\(O(nm^2)\\) to test isomorphism between two graphs with \\(m\\) vertices and \\(n\\) edges. The traditional approach for isomorphism testing has been to use the fact that the adjacency matrices (or incidence matrices or Laplace matrices) of isomorphic graphs are permutationally equivalent. The novelty in the author's approach is the efficient use of the fact that the pseudoinverses of these matrices are also permutationally equivalent. The pseudoinverse of a matrix \\(X\\) is taken as the matrix \\(X^+\\) giving a solution \\(\\overline {x} = X^+b\\) for the equations \\(Xx = b\\) which minimizes the squared error \\((b - Xx)^T (b - Xx)\\). If the \\(m \\times m\\) matrix \\(X\\) of rank \\(r\\) is factorizable as \\(X = UV\\), where \\(U\\) is \\(m \\times r\\) of rank \\(r\\) and \\(V\\) is \\(r \\times n\\) of rank \\(r\\), then \\(X^+ = V^+ U^+ = V^T(VV^T)^{-1} (U^TU)^{-1} U^T\\) can be readily computed.   Using a spanning tree of a graph (assumed connected), one gets a traditional canonical partition of the incidence matrix \\(M\\) as well as the Laplacian \\(MM^T = K\\) which facilitates the use of the above formula for the computation of \\(M^+\\) or \\(K^+\\). Concentrating on \\(K^+\\), the authors compute the diagonals of \\(K^+_1\\) and \\(K^+_2\\) (the \\(K^+\\) of the candidate graphs \\(G_1\\) and \\(G_2\\)) and use them to find a one-one correspondence between the vertices of \\(G_1\\) and \\(G_2\\). If this happens to be an isomorphism (preserves adjacencies) one is through. It is easier to detect non-isomorphism. An alternative approach of trying to match each column of \\(K^+_1\\) with a column of \\(K^+_2\\) iteratively has also been studied. This proves efficient in some cases.   The methods are illustrated with two examples. Inbuilt functions for pseudoinverses in `Mathematica' have been used.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1913583$39D62D3B-1EFF-4A45-8D25-BB3799D4B8AE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1913583$5A20FD8A-342F-477D-B28B-5E610E6FB0DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"de7887ac8896f76fb0219bbdc2f1520f3f1a5b3b","datavalue":{"value":"15A09","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1913583$50921C3A-239E-47E9-9C7C-902BFD80AAE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1913583$49AEB572-CABD-48B1-9C1B-3435739945B9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fbb8a3c3f02e132dc6e678a9ab5608fecbdcc36f","datavalue":{"value":"881182","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1913583$CD3F75DD-4AD2-410A-894C-A4127041784C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2af51969b73542d6aab2bcded7015ec65969c29e","datavalue":{"value":"heuristic algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1913583$FB1F530C-24E8-4A9D-BC09-14CA9419F3EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"39b8e6d57ec18c6b5c9be4cd40348585ad564e2f","datavalue":{"value":"isomorphism testing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1913583$830FBEF4-CED7-49CF-A597-ACAA6670FA9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"63eba4d8b476e80897cdd0308723882da491ff49","datavalue":{"value":"adjacency matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1913583$7E312827-7DB6-4185-AC88-A534E23904EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19572e1e24109e37d74cf8af5e25df5b706071d6","datavalue":{"value":"incidence matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1913583$14F426C5-BD2B-4C6F-85D8-37E4291F46C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7b4c30262eee0a09e72c325f94adb686779cb32","datavalue":{"value":"Laplace matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1913583$C09923CE-EF2C-4A61-A10E-1816B29FE521","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ae8c1b27ccc12bbe7293fcfec5e987c3f19dcfbd","datavalue":{"value":"pseudoinverses","type":"string"},"datatype":"string"},"type":"statement","id":"Q1913583$D3032A0E-EC61-482E-A226-A918B684167B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"849b7a0d6519fee636943d9bde0b8b557d98cf60","datavalue":{"value":"spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1913583$145D773E-6E24-4B5E-A807-22814219DB53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e41fb471c5632503b8716f23269ac7a1a49e160e","datavalue":{"value":"partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1913583$DC1D8B9E-2A2E-450E-BB51-622E32EE1398","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b07eec98772a8c24fb556e9a027cbd0c75ec516b","datavalue":{"value":"Laplacian","type":"string"},"datatype":"string"},"type":"statement","id":"Q1913583$44EDE97D-8981-4115-863C-56A578F1CBB4","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"d89eed7087f93c1cdf4120c868b02779d34eaa8b","datavalue":{"value":{"entity-type":"item","numeric-id":13309,"id":"Q13309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1913583$F972E11B-DC9D-40C6-A7B5-F381BF4A3E8D","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1913583$6E9F8E2C-2C26-4313-93A3-0E156F86C88A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9572428399dd6b77eef1d84a669c453a56a49b72","datavalue":{"value":{"entity-type":"item","numeric-id":2395579,"id":"Q2395579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1913583$62C4CB14-919C-4D83-8CD7-AD7B255DFD8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0b110cdae6ba1efeabcaa1dc910da29725bec83","datavalue":{"value":{"entity-type":"item","numeric-id":5515115,"id":"Q5515115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1913583$472ACDD8-093F-44EC-8941-628622E1E4E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c435d235f5dd5d88317484b4ce4d5923395e2745","datavalue":{"value":{"entity-type":"item","numeric-id":1165581,"id":"Q1165581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1913583$98B7DB90-2CE6-4DF9-A8CD-D58DEEAD7291","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e38aa336c4c4ba1f1e04ee9fcd013ff2380b03b9","datavalue":{"value":{"entity-type":"item","numeric-id":5820842,"id":"Q5820842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1913583$70511903-7545-4027-854F-B8E87853989C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c43b2b83a780a8ed53d9614e50854f622bbfb01","datavalue":{"value":{"entity-type":"item","numeric-id":5603271,"id":"Q5603271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1913583$998B7782-4C08-4488-9E66-3D62126D122A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73285fea223ea7d94c3268dc397030d833439617","datavalue":{"value":{"entity-type":"item","numeric-id":5588439,"id":"Q5588439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1913583$0EFAC347-89FA-4A0A-82E4-67276EACA7AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae3f853a816c990699349ba249f035d7e17ab4ec","datavalue":{"value":{"entity-type":"item","numeric-id":2515174,"id":"Q2515174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1913583$56A62DD1-369F-4C3D-A57E-75BDF7D41DE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"630f622126a505ffc3f1bc342a535bda80d265e1","datavalue":{"value":{"entity-type":"item","numeric-id":4000231,"id":"Q4000231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1913583$D33F8EDD-6358-4D1D-9EC1-63174F77147E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77f4010707a92fbabc7f0d15732be6046238ed19","datavalue":{"value":{"entity-type":"item","numeric-id":2764398,"id":"Q2764398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a22663706c7797169891b5a5b1ac3eca4a225378","datavalue":{"value":{"amount":"+0.7940718531608582","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1913583$0FBA579A-7CBE-40C9-800C-493BCC465A40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"220360f2e681c7f51682ef653dc643be6be844cb","datavalue":{"value":{"entity-type":"item","numeric-id":5242859,"id":"Q5242859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef5f27a0b71acaf72e3d803742e79b2614d1343c","datavalue":{"value":{"amount":"+0.7758739590644836","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1913583$6A175FD0-B70F-4009-9BA8-06ED38B46067","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c2c9e1cc4212a19fc0038eb4e691e3f48767a25","datavalue":{"value":{"entity-type":"item","numeric-id":5443268,"id":"Q5443268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a599eafcf94a4a35f235221e2432b540416d5666","datavalue":{"value":{"amount":"+0.7713249921798706","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1913583$2310548E-A309-436F-A2A4-A813484587E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60af1fe3d379e6bb4c556eb7cff42c289ed1eb79","datavalue":{"value":{"entity-type":"item","numeric-id":5146186,"id":"Q5146186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4dfb3f96403647a42c9a61a2a4296b0dfe99570","datavalue":{"value":{"amount":"+0.7646167278289795","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1913583$34E172A0-9712-44BF-8EFB-8702CCE53CC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57bc0450467e81597bf692894cb984dc1e45d9e0","datavalue":{"value":{"entity-type":"item","numeric-id":3542737,"id":"Q3542737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45c5080533f20bdebcff8df6a79684c3d573c3f3","datavalue":{"value":{"amount":"+0.7645894885063171","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1913583$BFBBE15C-7DFC-41B7-B646-E56327CFB089","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A graph isomorphism algorithm using pseudoinverses","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_graph_isomorphism_algorithm_using_pseudoinverses"}}}}}