{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,30]],"date-time":"2025-12-30T23:17:51Z","timestamp":1767136671265,"version":"build-2238731810"},"reference-count":35,"publisher":"Wiley","issue":"7","license":[{"start":{"date-parts":[[2019,8,16]],"date-time":"2019-08-16T00:00:00Z","timestamp":1565913600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/100014718","name":"Innovative Research Group Project of the National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["2017YFB1401302"],"award-info":[{"award-number":["2017YFB1401302"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014718","name":"Innovative Research Group Project of the National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["2017YFB0202200"],"award-info":[{"award-number":["2017YFB0202200"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014718","name":"Innovative Research Group Project of the National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61572260"],"award-info":[{"award-number":["61572260"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014718","name":"Innovative Research Group Project of the National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61872196"],"award-info":[{"award-number":["61872196"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006708","name":"Appalachian Regional Commission","doi-asserted-by":"publisher","award":["DE140100387"],"award-info":[{"award-number":["DE140100387"]}],"id":[{"id":"10.13039\/100006708","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006708","name":"Appalachian Regional Commission","doi-asserted-by":"publisher","award":["DE130100911"],"award-info":[{"award-number":["DE130100911"]}],"id":[{"id":"10.13039\/100006708","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Concurrency and Computation"],"published-print":{"date-parts":[[2021,4,10]]},"abstract":"<jats:title>Summary<\/jats:title>\n                  <jats:p>\n                    The graph isomorphism problem is to determine two finite graphs that are isomorphic which is not known with a polynomial\u2010time solution. This paper solves the simple undirected graph isomorphism problem with an algorithmic approach as NP=P and proposes a polynomial\u2010time solution to check if two simple undirected graphs are isomorphic or not. Three new representation methods of a graph as vertex\/edge adjacency matrix and triple tuple are proposed. A duality of edge and vertex and a reflexivity between vertex adjacency matrix and edge adjacency matrix were first introduced to present the core idea. Beyond this, the mathematical approval is based on an equivalence between permutation and bijection. Because only addition and multiplication operations satisfy the commutative law, we propose a permutation theorem to check fast whether one of two sets of arrays is a permutation of another or not. The permutation theorem was mathematically approved by Integer Factorization Theory, Pythagorean Triples Theorem, and Fundamental Theorem of Arithmetic. For each of two\n                    <jats:italic>n<\/jats:italic>\n                    \u2010ary arrays, the linear and squared sums of elements were respectively calculated to produce the results.\n                  <\/jats:p>","DOI":"10.1002\/cpe.5484","type":"journal-article","created":{"date-parts":[[2019,8,16]],"date-time":"2019-08-16T08:48:09Z","timestamp":1565945289000},"page":"1-1","update-policy":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["A polynomial\u2010time algorithm for simple undirected graph isomorphism"],"prefix":"10.1002","volume":"33","author":[{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0001-6488-1052","authenticated-orcid":false,"given":"Jing","family":"He","sequence":"first","affiliation":[{"name":"Institute of Information Technology Nanjing University of Finance and Economics  Nanjing China"},{"name":"Swinburne Data Science Research Institute Swinburne University of Technology  Melbourne Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0003-1677-9525","authenticated-orcid":false,"given":"Jinjun","family":"Chen","sequence":"additional","affiliation":[{"name":"Swinburne Data Science Research Institute Swinburne University of Technology  Melbourne Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0002-1821-8644","authenticated-orcid":false,"given":"Guangyan","family":"Huang","sequence":"additional","affiliation":[{"name":"School of Information Technology Deakin University  Melbourne Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jie","family":"Cao","sequence":"additional","affiliation":[{"name":"Institute of Information Technology Nanjing University of Finance and Economics  Nanjing China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhiwang","family":"Zhang","sequence":"additional","affiliation":[{"name":"Institute of Information Technology Nanjing University of Finance and Economics  Nanjing China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hui","family":"Zheng","sequence":"additional","affiliation":[{"name":"Swinburne Data Science Research Institute Swinburne University of Technology  Melbourne Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peng","family":"Zhang","sequence":"additional","affiliation":[{"name":"Swinburne Data Science Research Institute Swinburne University of Technology  Melbourne Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roozbeh","family":"Zarei","sequence":"additional","affiliation":[{"name":"Swinburne Data Science Research Institute Swinburne University of Technology  Melbourne Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ferry","family":"Sansoto","sequence":"additional","affiliation":[{"name":"Swinburne Data Science Research Institute Swinburne University of Technology  Melbourne Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ruchuan","family":"Wang","sequence":"additional","affiliation":[{"name":"Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks Nanjing University of Posts and Telecommunications  Nanjing China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yimu","family":"Ji","sequence":"additional","affiliation":[{"name":"Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks Nanjing University of Posts and Telecommunications  Nanjing China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weibei","family":"Fan","sequence":"additional","affiliation":[{"name":"Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks Nanjing University of Posts and Telecommunications  Nanjing China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhijun","family":"Xie","sequence":"additional","affiliation":[{"name":"Department of Information Science and Engineering Ningbo University  Ningbo China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiancheng","family":"Wang","sequence":"additional","affiliation":[{"name":"Ningbo Institute of Technology Zhejiang University  Ningbo China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0001-7029-5797","authenticated-orcid":false,"given":"Mengjiao","family":"Guo","sequence":"additional","affiliation":[{"name":"Swinburne Data Science Research Institute Swinburne University of Technology  Melbourne Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chi\u2010Hung","family":"Chi","sequence":"additional","affiliation":[{"name":"CSIRO  Tasmania Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paulo A.","family":"de Souza","sequence":"additional","affiliation":[{"name":"CSIRO  Tasmania Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiekui","family":"Zhang","sequence":"additional","affiliation":[{"name":"JingQi Smart Healthcare Pty Ltd  Hefei China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Youtao","family":"Li","sequence":"additional","affiliation":[{"name":"JingQi Smart Healthcare Pty Ltd  Hefei China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaojun","family":"Chen","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics The Hong Kong Polytechnic University  Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yong","family":"Shi","sequence":"additional","affiliation":[{"name":"Research Center on Fictitious Economy and Data Sciences, Chinese Academy of Sciences  Beijing China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Green","sequence":"additional","affiliation":[{"name":"Faculty of Information Technology Monash University  Melbourne Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Taraporewalla","family":"Kersi","sequence":"additional","affiliation":[{"name":"Royal Brisbane and Women's Hospital  Herston Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9","family":"Van Zundert","sequence":"additional","affiliation":[{"name":"Royal Brisbane and Women's Hospital  Herston Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2019,8,16]]},"reference":[{"key":"e_1_2_10_2_1","volume-title":"Computers and Intractability: A Guide to the Theory of np\u2010Completeness","author":"Garey MR","year":"1979"},{"key":"e_1_2_10_3_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.aad7416"},{"key":"e_1_2_10_4_1","unstructured":"KlarreichE.Landmark Algorithm Breaks 30\u2010Year Impasse. Quanta Magazine.2015."},{"key":"e_1_2_10_5_1","unstructured":"L Babai 2017"},{"issue":"3","key":"e_1_2_10_6_1","doi-asserted-by":"crossref","first-page":"477","DOI":"10.54870\/1551-3440.1166","article-title":"Graph isomorphisms and matrix similarity: switching between representations","volume":"6","author":"Dana\u2010Picard T","year":"2009","journal-title":"Math Enthus"},{"key":"e_1_2_10_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/120892234"},{"key":"e_1_2_10_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfranklin.2005.04.006"},{"key":"e_1_2_10_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00034-010-9248-7"},{"key":"e_1_2_10_10_1","doi-asserted-by":"crossref","unstructured":"FarahaniMM ChaharsoughiSK.A genetic and iterative local search algorithm for solving subgraph isomorphism problem. Paper presented at: 2015 International Conference on Industrial Engineering and Operations Management (IEOM);2015;Dubai United Arab Emirates.","DOI":"10.1109\/IEOM.2015.7093815"},{"key":"e_1_2_10_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0262-8856(95)91467-R"},{"key":"e_1_2_10_12_1","doi-asserted-by":"crossref","unstructured":"TeixeiraCHC FonsecaAJ SerafiniM SiganosG ZakiMJ AboulnagaA.Arabesque: a system for distributed graph mining. Paper presented at: Proceedings of the 25th Symposium on Operating Systems Principles;2015;Monterey CA.","DOI":"10.1145\/2815400.2815410"},{"key":"e_1_2_10_13_1","unstructured":"Permutation Wikipedia.https:\/\/2.zoppoz.workers.dev:443\/https\/en.wikipedia.org\/wiki\/Permutation"},{"key":"e_1_2_10_14_1","doi-asserted-by":"crossref","unstructured":"HopcroftJE WongJK.Linear time algorithm for isomorphism of planar graphs. In: Proceedings of the 6th Annual ACM Symposium on Theory of Computing;1974;Seattle WA.","DOI":"10.1145\/800119.803896"},{"key":"e_1_2_10_15_1","volume-title":"The Design and Analysis of Computer Algorithms","author":"Aho AV","year":"1974"},{"key":"e_1_2_10_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210015"},{"key":"e_1_2_10_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90009-5"},{"key":"e_1_2_10_18_1","volume-title":"Practical Graph Isomorphism","author":"McKay BD","year":"1981"},{"key":"e_1_2_10_19_1","doi-asserted-by":"crossref","unstructured":"L\u00f3pez\u2010PresaJL AntaAF.Fast algorithm for graph isomorphism testing. Paper presented at: International Symposium on Experimental Algorithms;2009;Dortmund Germany.","DOI":"10.1007\/978-3-642-02011-7_21"},{"key":"e_1_2_10_20_1","unstructured":"L\u00f3pez\u2010PresaJL AntaAF ChiroqueLN.Conauto\u20102.0: fast isomorphism testing and automorphism group computation. arXiv preprint arXiv: 1108.1060.2011."},{"key":"e_1_2_10_21_1","unstructured":"CordellaLP FoggiaP SansoneC VentoM.An improved algorithm for matching large graphs. Paper presented at: 3rd IAPR\u2010TC15 Workshop on Graph\u2010Based Representations in Pattern Recognition;2001;Ischia Italy."},{"key":"e_1_2_10_22_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001497000081"},{"key":"e_1_2_10_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/321958.321963"},{"key":"e_1_2_10_24_1","unstructured":"CordellaLP FoggiaP SansoneC VentoM.Evaluating performance of the VF graph matching algorithm. In: Proceedings of the 10th International Conference on Image Analysis and Processing;1999;Venice Italy."},{"issue":"6","key":"e_1_2_10_25_1","article-title":"Graph invariants and graph isomorphism","volume":"3","author":"Balpande V","year":"2012","journal-title":"IJCTA"},{"issue":"4","key":"e_1_2_10_26_1","first-page":"1","article-title":"An approach of graph isomorphism detection based on vertex\u2010invariant","volume":"4","author":"Balpande V","year":"2015","journal-title":"Int J Adv Stud Comput Sci Eng"},{"key":"e_1_2_10_27_1","doi-asserted-by":"publisher","DOI":"10.1080\/10020070512331341960"},{"key":"e_1_2_10_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0303-2647(99)00041-6"},{"key":"e_1_2_10_29_1","doi-asserted-by":"crossref","unstructured":"BabaiL.Graph isomorphism in quasipolynomial time [extended abstract]. In: Proceedings of the 48th Annual ACM Symposium on Theory of Computing;2016;Cambridge MA.","DOI":"10.1145\/2897518.2897542"},{"key":"e_1_2_10_30_1","unstructured":"Graph Isomorphism Wikipedia.https:\/\/2.zoppoz.workers.dev:443\/https\/en.wikipedia.org\/wiki\/Graph_isomorphism"},{"key":"e_1_2_10_31_1","unstructured":"Isomorphism Wikipedia.https:\/\/2.zoppoz.workers.dev:443\/https\/en.wikipedia.org\/wiki\/Isomorphism"},{"key":"e_1_2_10_32_1","unstructured":"Degree Sequence.https:\/\/2.zoppoz.workers.dev:443\/http\/www.math.unm.edu\/~loring\/links\/graph_s09\/degreeSeq.pdf"},{"key":"e_1_2_10_33_1","volume-title":"The Genesis of the Abstract Group Concept: A Contribution to the History of the Origin of Abstract Group Theory","author":"Wussing H","year":"2007"},{"key":"e_1_2_10_34_1","unstructured":"Adjacency Matrix Wikipedia.https:\/\/2.zoppoz.workers.dev:443\/https\/en.wikipedia.org\/wiki\/Adjacency_matrix"},{"key":"e_1_2_10_35_1","volume-title":"A Friendly Introduction to Number Theory","author":"Silverman JH","year":"2006"},{"key":"e_1_2_10_36_1","unstructured":"Fundamental Theorem of Arithmetic.https:\/\/2.zoppoz.workers.dev:443\/https\/en.wikipedia.org\/wiki\/Fundamental_theorem_of_arithmetic"}],"updated-by":[{"DOI":"10.1002\/cpe.6599","type":"erratum","label":"Erratum","source":"publisher","updated":{"date-parts":[[2021,9,27]],"date-time":"2021-09-27T00:00:00Z","timestamp":1632700800000}}],"container-title":["Concurrency and Computation: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpe.5484","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/cpe.5484","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpe.5484","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,8]],"date-time":"2024-07-08T19:55:47Z","timestamp":1720468547000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/onlinelibrary.wiley.com\/doi\/10.1002\/cpe.5484"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,16]]},"references-count":35,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2021,4,10]]}},"alternative-id":["10.1002\/cpe.5484"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1002\/cpe.5484","archive":["Portico"],"relation":{},"ISSN":["1532-0626","1532-0634"],"issn-type":[{"value":"1532-0626","type":"print"},{"value":"1532-0634","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,8,16]]},"assertion":[{"value":"2018-12-23","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-06","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-08-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}