{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T00:40:02Z","timestamp":1736210402947,"version":"3.32.0"},"reference-count":36,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2018,8,8]],"date-time":"2018-08-08T00:00:00Z","timestamp":1533686400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"The National Key Research and Development Program of China","award":["2016YFB0200401"]},{"name":"National Science Foundation (NSF) China","award":["61402492, 61402486, 61379146"]},{"name":"the laboratory pre-research fund","award":["9140C810106150C81001"]},{"name":"the HUNAN Province Science Foundation","award":["2017RS3045"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"The isomorphism problem involves judging whether two graphs are topologically the same and producing structure-preserving isomorphism mapping. It is widely used in various areas. Diverse algorithms have been proposed to solve this problem in polynomial time, with the help of quantum walks. Some of these algorithms, however, fail to find the isomorphism mapping. Moreover, most algorithms have very limited performance on regular graphs which are generally difficult to deal with due to their symmetry. We propose IsoMarking to discover an isomorphism mapping effectively, based on the quantum walk which is sensitive to topological structures. Firstly, IsoMarking marks vertices so that it can reduce the harmful influence of symmetry. Secondly, IsoMarking can ascertain whether the current candidate bijection is consistent with existing bijections and eventually obtains qualified mapping. Thirdly, our experiments on 1585 pairs of graphs demonstrate that our algorithm performs significantly better on both ordinary graphs and regular graphs.<\/jats:p>","DOI":"10.3390\/e20080586","type":"journal-article","created":{"date-parts":[[2018,8,9]],"date-time":"2018-08-09T07:33:48Z","timestamp":1533800028000},"page":"586","source":"Crossref","is-referenced-by-count":3,"title":["Marking Vertices to Find Graph Isomorphism Mapping Based on Continuous-Time Quantum Walk"],"prefix":"10.3390","volume":"20","author":[{"given":"Xin","family":"Wang","sequence":"first","affiliation":[{"name":"College of Computer Science, National University of Defense Technology, Changsha 410073, China"},{"name":"Science and Technology on Parallel and Distributed Processing Laboratory, National University of Defense Technology, Changsha 410073, China"}]},{"given":"Yi","family":"Zhang","sequence":"additional","affiliation":[{"name":"College of Computer Science, National University of Defense Technology, Changsha 410073, China"}]},{"given":"Kai","family":"Lu","sequence":"additional","affiliation":[{"name":"College of Computer Science, National University of Defense Technology, Changsha 410073, China"},{"name":"Science and Technology on Parallel and Distributed Processing Laboratory, National University of Defense Technology, Changsha 410073, China"}]},{"given":"Xiaoping","family":"Wang","sequence":"additional","affiliation":[{"name":"College of Computer Science, National University of Defense Technology, Changsha 410073, China"},{"name":"Science and Technology on Parallel and Distributed Processing Laboratory, National University of Defense Technology, Changsha 410073, China"}]},{"given":"Kai","family":"Liu","sequence":"additional","affiliation":[{"name":"College of Computer Science, National University of Defense Technology, Changsha 410073, China"},{"name":"Science and Technology on Parallel and Distributed Processing Laboratory, National University of Defense Technology, Changsha 410073, China"}]}],"member":"1968","published-online":{"date-parts":[[2018,8,8]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/j.patcog.2014.01.002","article-title":"A long trip in the charming world of graphs for Pattern Recognition","volume":"48","author":"Vento","year":"2015","journal-title":"Pattern Recognit."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1450001","DOI":"10.1142\/S0218001414500013","article-title":"Graph matching and learning in pattern recognition in the last 10 years","volume":"28","author":"Foggia","year":"2014","journal-title":"Int. J. Pattern Recognit. Artif. Intell."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1142\/S0218001404003228","article-title":"Thirty years of graph matching in pattern recognition","volume":"18","author":"Conte","year":"2004","journal-title":"Int. J. Pattern Recognit. Artif. Intell."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Hsieh, S.M., Hsu, C.C., and Hsu, L.F. (2006). Efficient Method to Perform Isomorphism Testing of Labeled Graphs, Springer.","DOI":"10.1007\/11751649_46"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1471-2105-14-S7-S13","article-title":"A subgraph isomorphism algorithm and its application to biochemical data","volume":"14","author":"Bonnici","year":"2013","journal-title":"BMC Bioinform."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Cook, D.J., and Holder, L.B. (2006). Mining Graph Data, John Wiley & Sons.","DOI":"10.1002\/0470073047"},{"key":"ref_7","unstructured":"Baird, H.S., and Cho, Y.E. An artwork design verification system. Proceedings of the 12th Design Automation Conference."},{"key":"ref_8","unstructured":"Brugger, A., Bunke, H., Dickinson, P., and Riesen, K. Generalized Graph Matching for Data Mining and Information Retrieval. Proceedings of the Industrial Conference on Advances in Data Mining: Medical Applications, E-Commerce, Marketing, and Theoretical Aspects."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Kandel, A., Bunke, H., and Last, M. (2007). Applied Graph Theory in Computer Vision and Pattern Recognition, Springer.","DOI":"10.1007\/978-3-540-68020-8"},{"key":"ref_10","first-page":"82","article-title":"Graph matching: Theoretical foundations, algorithms, and applications","volume":"21","author":"Bunke","year":"2000","journal-title":"Proc. Vis. Interface"},{"key":"ref_11","unstructured":"Garey, M.R., and Johnson, D.S. (1983). Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1367","DOI":"10.1109\/TPAMI.2004.75","article-title":"A (sub)graph isomorphism algorithm for matching large graphs","volume":"26","author":"Cordella","year":"2004","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"804","DOI":"10.1109\/TPAMI.2017.2696940","article-title":"Challenging the Time Complexity of Exact Subgraph Isomorphism for Huge and Dense Graphs with VF3","volume":"40","author":"Carletti","year":"2018","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_14","unstructured":"Foggia, P., Liu, C.L., and Vento, M. (2017). Introducing VF3: A New Algorithm for Subgraph Isomorphism. Graph-Based Representations in Pattern Recognition, Springer International Publishing."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1016\/j.artint.2010.05.002","article-title":"AllDifferent -based filtering for subgraph isomorphism","volume":"174","author":"Solnon","year":"2010","journal-title":"Artif. Intell."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1100","DOI":"10.1109\/TPAMI.2005.138","article-title":"Exact and approximate graph matching using random walks","volume":"27","author":"Gori","year":"2005","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Babai, L. (2016, January 19\u201321). Graph isomorphism in quasipolynomial time [extended abstract]. Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, Cambridge, MA, USA.","DOI":"10.1145\/2897518.2897542"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"915","DOI":"10.1103\/PhysRevA.58.915","article-title":"Quantum computation and decision trees","volume":"58","author":"Farhi","year":"1998","journal-title":"Phys. Rev. A"},{"key":"ref_19","unstructured":"Feynman, R.P., Hibbs, A.R., and Weiss, G.H. (1965). Quantum Mechanics and Path Integrals, McGraw-Hill."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"075303","DOI":"10.1088\/1751-8113\/41\/7\/075303","article-title":"A Classical approach to the graph isomorphism problem using quantum walks","volume":"41","author":"Douglas","year":"2008","journal-title":"J. Phys. A"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"985","DOI":"10.1016\/j.patcog.2008.09.001","article-title":"Graph matching using the interference of continuous-time quantum walks","volume":"42","author":"Emms","year":"2009","journal-title":"Pattern Recognit."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"934","DOI":"10.1016\/j.imavis.2008.10.013","article-title":"Graph matching using the interference of discrete-time quantum walks","volume":"27","author":"Emms","year":"2009","journal-title":"Image Vis. Comput."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"045305","DOI":"10.1088\/1751-8113\/45\/4\/045305","article-title":"continuous-time quantum walk","volume":"45","author":"Qiang","year":"2012","journal-title":"J. Phys. A"},{"key":"ref_24","unstructured":"Qiang, X. (2011). The Research of Graph Isomorphism Algorithm Based on Quantum Walk. [Master\u2019s Thesis, National University of Defense Technology]. (In Chinese)."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Childs, A.M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., and Spielman, D.A. (2003, January 9\u201311). Exponential algorithmic speedup by a quantum walk. Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, San Diego, CA, USA.","DOI":"10.1145\/780542.780552"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1103\/PhysRevA.67.052307","article-title":"Quantum random-walk search algorithm","volume":"67","author":"Shenvi","year":"2003","journal-title":"Phys. Rev. A"},{"key":"ref_27","unstructured":"Santha, M. (2008, January 25\u201329). Quantum walk based search algorithms. Proceedings of the International Conference on Theory and Applications of Models of Computation, Xi\u2019an, Xi\u2019an, China."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"032320","DOI":"10.1103\/PhysRevA.92.032320","article-title":"Faster Quantum Walk Search on a Weighted Graph","volume":"92","author":"Wong","year":"2015","journal-title":"Phys. Rev. A"},{"key":"ref_29","first-page":"1109","article-title":"Quantum algorithms for the triangle problem","volume":"37","author":"Magniez","year":"2005","journal-title":"SIAM J. Comput."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"050304","DOI":"10.1088\/1674-1056\/22\/5\/050304","article-title":"Finding tree symmetries using continuous-time quantum walk","volume":"22","author":"Wu","year":"2013","journal-title":"Chin. Phys. B"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1137\/S0097539705447311","article-title":"Quantum Walk Algorithm for Element Distinctness","volume":"37","author":"Ambainis","year":"2007","journal-title":"SIAM J. Comput."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"022815","DOI":"10.1103\/PhysRevE.91.022815","article-title":"Measuring graph similarity through continuous-time quantum walks and the quantum Jensen-Shannon divergence","volume":"91","author":"Rossi","year":"2015","journal-title":"Phys. Rev. E Stat. Nonlinear Soft Matter Phys."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Bai, L., Rossi, L., Ren, P., Zhang, Z., and Hancock, E.R. (2015, January 13\u201315). A Quantum Jensen-Shannon Graph Kernel Using Discrete-Time Quantum Walks. Proceedings of the International Workshop on Graph-Based Representations in Pattern Recognition, Vienna, Austria.","DOI":"10.1007\/978-3-319-18224-7_25"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"032806","DOI":"10.1103\/PhysRevE.88.032806","article-title":"Characterizing graph symmetries through quantum Jensen-Shannon divergence","volume":"88","author":"Rossi","year":"2013","journal-title":"Phys. Rev. E Stat. Nonlinear Soft Matter Phys."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0020-0190(79)90004-8","article-title":"A note on the graph isomorphism counting problem","volume":"8","author":"Mathon","year":"1979","journal-title":"Inf. Process. Lett."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Pelillo, M. (1995, January 26\u201328). Relaxation labeling networks that solve the maximum clique problem. Proceedings of the 4th International Conference on Artificial Neural Networks, Cambridge, UK.","DOI":"10.1049\/cp:19950548"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/20\/8\/586\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T00:19:15Z","timestamp":1736209155000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/20\/8\/586"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,8]]},"references-count":36,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2018,8]]}},"alternative-id":["e20080586"],"URL":"https:\/\/doi.org\/10.3390\/e20080586","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2018,8,8]]}}}