{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,5]],"date-time":"2026-04-05T20:36:15Z","timestamp":1775421375703,"version":"3.50.1"},"reference-count":71,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,7,15]],"date-time":"2019-07-15T00:00:00Z","timestamp":1563148800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,7,15]],"date-time":"2019-07-15T00:00:00Z","timestamp":1563148800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2020,1]]},"DOI":"10.1007\/s00778-019-00544-1","type":"journal-article","created":{"date-parts":[[2019,7,15]],"date-time":"2019-07-15T10:51:44Z","timestamp":1563187904000},"page":"419-458","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":49,"title":["Comparing heuristics for graph edit distance computation"],"prefix":"10.1007","volume":"29","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8651-750X","authenticated-orcid":false,"given":"David B.","family":"Blumenthal","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0548-4257","authenticated-orcid":false,"given":"Nicolas","family":"Boria","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7128-507X","authenticated-orcid":false,"given":"Johann","family":"Gamper","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4581-7570","authenticated-orcid":false,"given":"S\u00e9bastien","family":"Bougleux","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1658-0527","authenticated-orcid":false,"given":"Luc","family":"Brun","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,7,15]]},"reference":[{"key":"544_CR1","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.patrec.2017.10.007","volume":"100","author":"Z Abu-Aisheh","year":"2017","unstructured":"Abu-Aisheh, Z., Ga\u00fczere, B., Bougleux, S., Ramel, J.Y., Brun, L., Raveaux, R., H\u00e9roux, P., Adam, S.: Graph edit distance contest 2016: results and future challenges. Pattern Recognit. Lett. 100, 96\u2013103 (2017). \nhttps:\/\/doi.org\/10.1016\/j.patrec.2017.10.007","journal-title":"Pattern Recognit. Lett."},{"key":"544_CR2","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1007\/978-3-319-18224-7_14","volume-title":"Graph-Based Representations in Pattern Recognition","author":"Zeina Abu-Aisheh","year":"2015","unstructured":"Abu-Aisheh, Z., Raveaux, R., Ramel, J.: A graph database repository and performance evaluation metrics for graph edit distance. In: Liu, C., Luo, B., Kropatsch, W.G., Cheng, J. (eds.) GbRPR 2015, LNCS, vol. 9069. Springer, Cham, pp. 138\u2013147 (2015). \nhttps:\/\/doi.org\/10.1007\/978-3-319-18224-7_14"},{"key":"544_CR3","doi-asserted-by":"publisher","unstructured":"Babai, L.: Graph isomorphism in quasipolynomial time [extended abstract]. In: Wichs, D., Mansour, Y. (eds.) STOC 2016. ACM, New York, pp. 684\u2013697 (2016). \nhttps:\/\/doi.org\/10.1145\/2897518.2897542","DOI":"10.1145\/2897518.2897542"},{"key":"544_CR4","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/978-3-319-97785-0_28","volume-title":"Lecture Notes in Computer Science","author":"David B. Blumenthal","year":"2018","unstructured":"Blumenthal, D.B., Bougleux, S., Gamper, J., Brun, L.: Ring based approximation of graph edit distance. In: Bai, X., Hancock, E., Ho, T., Wilson, R., Biggio, B., Robles-Kelly, A. (eds.) S+SSPR 2018, LNCS, vol. 11004. Springer, Cham, pp. 293\u2013303 (2018). \nhttps:\/\/doi.org\/10.1007\/978-3-319-97785-0_28"},{"key":"544_CR5","unstructured":"Blumenthal, D.B., Bougleux, S., Gamper, J., Brun, L.: Upper bounding GED via transformations to LSAPE based on rings and machine learning (2019)"},{"key":"544_CR6","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/978-3-030-20081-7_2","volume-title":"Graph-Based Representations in Pattern Recognition","author":"David B. Blumenthal","year":"2019","unstructured":"Blumenthal, D.B., Bougleux, S., Gamper, J., Brun, L.: GEDLIB: a C++ library for graph edit distance computation. In: Conte, D., Ramel, J.Y., Foggia, P. (eds.) Graph-Based Representations in Pattern Recognition. GbRPR 2019. Lecture Notes in Computer Science, vol. 11510, pp. 14\u201324. Springer, Cham (2019)"},{"key":"544_CR7","doi-asserted-by":"publisher","unstructured":"Blumenthal, D.B., Daller, E., Bougleux, S., Brun, L., Gamper, J.: Quasimetric graph edit distance as a compact quadratic assignment problem. In: ICPR 2018. IEEE Computer Society, pp. 934\u2013939 (2018). \nhttps:\/\/doi.org\/10.1109\/ICPR.2018.8546055","DOI":"10.1109\/ICPR.2018.8546055"},{"key":"544_CR8","doi-asserted-by":"publisher","unstructured":"Blumenthal, D.B., Gamper, J.: Correcting and speeding-up bounds for non-uniform graph edit distance. In: ICDE 2017. IEEE Computer Society, pp. 131\u2013134 (2017). \nhttps:\/\/doi.org\/10.1109\/ICDE.2017.57","DOI":"10.1109\/ICDE.2017.57"},{"issue":"3","key":"544_CR9","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1109\/TKDE.2017.2772243","volume":"30","author":"DB Blumenthal","year":"2018","unstructured":"Blumenthal, D.B., Gamper, J.: Improved lower bounds for graph edit distance. IEEE Trans. Knowl. Data Eng. 30(3), 503\u2013516 (2018). \nhttps:\/\/doi.org\/10.1109\/TKDE.2017.2772243","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"544_CR10","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2018.05.002","author":"DB Blumenthal","year":"2018","unstructured":"Blumenthal, D.B., Gamper, J.: On the exact computation of the graph edit distance. Pattern Recognit. Lett. (2018). \nhttps:\/\/doi.org\/10.1016\/j.patrec.2018.05.002","journal-title":"Pattern Recognit. Lett."},{"issue":"5","key":"544_CR11","doi-asserted-by":"publisher","first-page":"1170","DOI":"10.1086\/228631","volume":"92","author":"P Bonacich","year":"1987","unstructured":"Bonacich, P.: Power and centrality: a family of measures. Am. J. Sociol. 92(5), 1170\u20131182 (1987). \nhttps:\/\/doi.org\/10.1086\/228631","journal-title":"Am. J. Sociol."},{"key":"544_CR12","unstructured":"Boria, N., Blumenthal, D.B., Bougleux, S., Brun, L.: Improved local search for graph edit distance (2019). Submitted. \narXiv:1907.02929"},{"key":"544_CR13","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/978-3-319-97785-0_44","volume-title":"Lecture Notes in Computer Science","author":"Nicolas Boria","year":"2018","unstructured":"Boria, N., Bougleux, S., Brun, L.: Approximating GED using a stochastic generator and multistart IPFP. In: Bai, X., Hancock, E.R., Ho, T.K., Wilson, R.C., Biggio, B., Robles-Kelly, A. (eds.) S+SSPR 2018. Springer, Cham, pp. 460\u2013469 (2018). \nhttps:\/\/doi.org\/10.1007\/978-3-319-97785-0_44"},{"key":"544_CR14","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/j.patrec.2016.10.001","volume":"87","author":"S Bougleux","year":"2017","unstructured":"Bougleux, S., Brun, L., Carletti, V., Foggia, P., Ga\u00fcz\u00e8re, B., Vento, M.: Graph edit distance as a quadratic assignment problem. Pattern Recognit. Lett. 87, 38\u201346 (2017). \nhttps:\/\/doi.org\/10.1016\/j.patrec.2016.10.001","journal-title":"Pattern Recognit. Lett."},{"key":"544_CR15","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2018.03.032","author":"S Bougleux","year":"2018","unstructured":"Bougleux, S., Ga\u00fcz\u00e8re, B., Blumenthal, D.B., Brun, L.: Fast linear sum assignment with error-correction and no cost constraints. Pattern Recognit. Lett. (2018). \nhttps:\/\/doi.org\/10.1016\/j.patrec.2018.03.032","journal-title":"Pattern Recognit. Lett."},{"key":"544_CR16","doi-asserted-by":"publisher","unstructured":"Bougleux, S., Ga\u00fcz\u00e8re, B., Brun, L.: Graph edit distance as a quadratic program. In: ICPR 2016. IEEE Computer Society, pp. 1701\u20131706 (2016). \nhttps:\/\/doi.org\/10.1109\/ICPR.2016.7899881","DOI":"10.1109\/ICPR.2016.7899881"},{"key":"544_CR17","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/978-3-319-58961-9_11","volume-title":"Graph-Based Representations in Pattern Recognition","author":"S\u00e9bastien Bougleux","year":"2017","unstructured":"Bougleux, S., Ga\u00fcz\u00e8re, B., Brun, L.: A Hungarian algorithm for error-correcting graph matching. In: Foggia, P., Liu, C., Vento, M. (eds.) GbRPR 2017, LNCS, vol. 10310. Springer, Cham, pp. 118\u2013127 (2017). \nhttps:\/\/doi.org\/10.1007\/978-3-319-58961-9_11"},{"issue":"1\u20137","key":"544_CR18","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0169-7552(98)00110-X","volume":"30","author":"S Brin","year":"1998","unstructured":"Brin, S., Page, L.: The anatomy of a large-scale hypertextual web search engine. Comput. Netw. 30(1\u20137), 107\u2013117 (1998). \nhttps:\/\/doi.org\/10.1016\/S0169-7552(98)00110-X","journal-title":"Comput. Netw."},{"key":"544_CR19","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2018.03.016","author":"L Brun","year":"2018","unstructured":"Brun, L., Foggia, P., Vento, M.: Trends in graph-based representations for pattern recognition. Pattern Recognit. Lett. (2018). \nhttps:\/\/doi.org\/10.1016\/j.patrec.2018.03.016","journal-title":"Pattern Recognit. Lett."},{"issue":"4","key":"544_CR20","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/0167-8655(83)90033-8","volume":"1","author":"H Bunke","year":"1983","unstructured":"Bunke, H., Allermann, G.: Inexact graph matching for structural pattern recognition. Pattern Recognit. Lett. 1(4), 245\u2013253 (1983). \nhttps:\/\/doi.org\/10.1016\/0167-8655(83)90033-8","journal-title":"Pattern Recognit. Lett."},{"key":"544_CR21","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/978-3-319-18224-7_19","volume-title":"Graph-Based Representations in Pattern Recognition","author":"Vincenzo Carletti","year":"2015","unstructured":"Carletti, V., Ga\u00fcz\u00e8re, B., Brun, L., Vento, M.: Approximate graph edit distance computation combining bipartite matching and exact neighborhood substructure distance. In: Liu, C., Luo, B., Kropatsch, W.G., Cheng, J. (eds.) GbRPR 2015, LNCS, vol. 9069. Springer, Cham, pp. 188\u2013197 (2015). \nhttps:\/\/doi.org\/10.1007\/978-3-319-18224-7_19"},{"issue":"3","key":"544_CR22","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1145\/1961189.1961199","volume":"2","author":"CC Chang","year":"2011","unstructured":"Chang, C.C., Lin, C.J.: LIBSVM: a library for support vector machines. ACM Trans. Intell. Syst. Technol. 2(3), 27 (2011). \nhttps:\/\/doi.org\/10.1145\/1961189.1961199","journal-title":"ACM Trans. Intell. Syst. Technol."},{"issue":"3","key":"544_CR23","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1142\/S0218001404003228","volume":"18","author":"D Conte","year":"2004","unstructured":"Conte, D., Foggia, P., Sansone, C., Vento, M.: Thirty years of graph matching in pattern recognition. Int. J. Pattern Recognit. Artif. Intell. 18(3), 265\u2013298 (2004). \nhttps:\/\/doi.org\/10.1142\/S0218001404003228","journal-title":"Int. J. Pattern Recognit. Artif. Intell."},{"issue":"10","key":"544_CR24","doi-asserted-by":"publisher","first-page":"1367","DOI":"10.1109\/TPAMI.2004.75","volume":"26","author":"LP Cordella","year":"2004","unstructured":"Cordella, L.P., Foggia, P., Sansone, C., Vento, M.: A (sub)graph isomorphism algorithm for matching large graphs. IEEE Trans. Pattern Anal. Mach. Intell. 26(10), 1367\u20131372 (2004). \nhttps:\/\/doi.org\/10.1109\/TPAMI.2004.75","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"544_CR25","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/978-3-319-18224-7_23","volume-title":"Graph-Based Representations in Pattern Recognition","author":"Xavier Cort\u00e9s","year":"2015","unstructured":"Cort\u00e9s, X., Serratosa, F., Moreno-Garc\u00eda, C.F.: On the influence of node centralities on graph edit distance for graph classification. In: Liu, C., Luo, B., Kropatsch, W.G., Cheng, J. (eds.) GbRPR 2015, LNCS, vol. 9069. Springer, Cham, pp. 231\u2013241 (2015). \nhttps:\/\/doi.org\/10.1007\/978-3-319-18224-7_23"},{"key":"544_CR26","doi-asserted-by":"publisher","unstructured":"Daller, \u00c9., Bougleux, S., Ga\u00fcz\u00e8re, B., Brun, L.: Approximate graph edit distance by several local searches in parallel. In: Fred, A., di\u00a0Baja, G.S., Marsico, M.D. (eds.) ICPRAM 2018. SciTePress, pp. 149\u2013158 (2018). \nhttps:\/\/doi.org\/10.5220\/0006599901490158","DOI":"10.5220\/0006599901490158"},{"key":"544_CR27","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/978-3-319-18224-7_8","volume-title":"Graph-Based Representations in Pattern Recognition","author":"Miquel Ferrer","year":"2015","unstructured":"Ferrer, M., Serratosa, F., Riesen, K.: A first step towards exact graph edit distance using bipartite graph matching. In: Liu, C., Luo, B., Kropatsch, W.G., Cheng, J. (eds.) GbRPR 2015, LNCS, vol. 9069. Springer, Cham, pp. 77\u201386 (2015). \nhttps:\/\/doi.org\/10.1007\/978-3-319-18224-7_8"},{"issue":"2","key":"544_CR28","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/j.patcog.2014.07.015","volume":"48","author":"A Fischer","year":"2015","unstructured":"Fischer, A., Suen, C.Y., Frinken, V., Riesen, K., Bunke, H.: Approximation of graph edit distance based on Hausdorff matching. Pattern Recognit. 48(2), 331\u2013343 (2015). \nhttps:\/\/doi.org\/10.1016\/j.patcog.2014.07.015","journal-title":"Pattern Recognit."},{"issue":"1","key":"544_CR29","doi-asserted-by":"publisher","first-page":"1450001:1","DOI":"10.1142\/S0218001414500013","volume":"28","author":"P Foggia","year":"2014","unstructured":"Foggia, P., Percannella, G., Vento, M.: Graph matching and learning in pattern recognition in the last 10 years. Int. J. Pattern Recognit. Artif. Intell. 28(1), 1450001:1\u20131450001:40 (2014). \nhttps:\/\/doi.org\/10.1142\/S0218001414500013","journal-title":"Int. J. Pattern Recognit. Artif. Intell."},{"issue":"1\u20132","key":"544_CR30","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1002\/nav.3800030109","volume":"3","author":"M Frank","year":"1956","unstructured":"Frank, M., Wolfe, P.: An algorithm for quadratic programming. Nav. Res. Logist. Q. 3(1\u20132), 95\u2013110 (1956). \nhttps:\/\/doi.org\/10.1002\/nav.3800030109","journal-title":"Nav. Res. Logist. Q."},{"issue":"1","key":"544_CR31","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s10044-008-0141-y","volume":"13","author":"X Gao","year":"2010","unstructured":"Gao, X., Xiao, B., Tao, D., Li, X.: A survey of graph edit distance. Pattern Anal. Appl. 13(1), 113\u2013129 (2010). \nhttps:\/\/doi.org\/10.1007\/s10044-008-0141-y","journal-title":"Pattern Anal. Appl."},{"key":"544_CR32","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/978-3-662-44415-3_8","volume-title":"Lecture Notes in Computer Science","author":"Benoit Ga\u00fcz\u00e8re","year":"2014","unstructured":"Ga\u00fcz\u00e8re, B., Bougleux, S., Riesen, K., Brun, L.: Approximate graph edit distance guided by bipartite matching of bags of walks. In: Fr\u00e4nti, P., Brown, G., Loog, M., Escolano, F., Pelillo, M. (eds.) S+SSPR 2014, LNCS, vol. 8621. Springer, Cham, pp. 73\u201382 (2014). \nhttps:\/\/doi.org\/10.1007\/978-3-662-44415-3_8"},{"key":"544_CR33","unstructured":"Guennebaud, G., Jacob, B., et\u00a0al.: Eigen v3 (2010). \nhttp:\/\/eigen.tuxfamily.org\n\n. Accessed 5 July 2019"},{"key":"544_CR34","unstructured":"Gurobi Optimization LLC: Gurobi Optimizer Reference Manual. \nhttp:\/\/www.gurobi.com\n\n. Accessed 5 July 2019"},{"key":"544_CR35","volume-title":"Classification and Uses of Finger Prints","author":"ER Henry","year":"1900","unstructured":"Henry, E.R.: Classification and Uses of Finger Prints. Routledge, London (1900)"},{"issue":"8","key":"544_CR36","doi-asserted-by":"publisher","first-page":"1200","DOI":"10.1109\/TPAMI.2006.152","volume":"28","author":"D Justice","year":"2006","unstructured":"Justice, D., Hero, A.: A binary linear programming formulation of the graph edit distance. IEEE Trans. Pattern Anal. Mach. Intell. 28(8), 1200\u20131214 (2006). \nhttps:\/\/doi.org\/10.1109\/TPAMI.2006.152","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"4","key":"544_CR37","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N Karmarkar","year":"1984","unstructured":"Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica 4(4), 373\u2013396 (1984). \nhttps:\/\/doi.org\/10.1007\/BF02579150","journal-title":"Combinatorica"},{"issue":"1\u20132","key":"544_CR38","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"HW Kuhn","year":"1955","unstructured":"Kuhn, H.W.: The Hungarian method for the assignment problem. Nav. Res. Logist. Q. 2(1\u20132), 83\u201397 (1955). \nhttps:\/\/doi.org\/10.1002\/nav.3800020109","journal-title":"Nav. Res. Logist. Q."},{"issue":"4","key":"544_CR39","doi-asserted-by":"publisher","first-page":"44:1","DOI":"10.1145\/1916461.1916468","volume":"37","author":"S Le Digabel","year":"2011","unstructured":"Le Digabel, S.: Algorithm 909: NOMAD: nonlinear optimization with the MADS algorithm. ACM Trans. Math. Softw. 37(4), 44:1\u201344:15 (2011). \nhttps:\/\/doi.org\/10.1145\/1916461.1916468","journal-title":"ACM Trans. Math. Softw."},{"key":"544_CR40","doi-asserted-by":"publisher","unstructured":"Le\u00a0Gall, F.: Powers of tensors and fast matrix multiplication. In: Nabeshima, K., Nagasaka, K., Winkler, F., Sz\u00e1nt\u00f3, \u00c1. (eds.) ISSAC 2014. ACM, pp. 296\u2013303 (2014). \nhttps:\/\/doi.org\/10.1145\/2608628.2608664","DOI":"10.1145\/2608628.2608664"},{"key":"544_CR41","volume-title":"The Boost Graph Library: User Guide and Reference Manual","author":"L Lee","year":"2002","unstructured":"Lee, L., Lumsdaine, A., Siek, J.: The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley Longman, Boston (2002)"},{"key":"544_CR42","unstructured":"Leordeanu, M., Hebert, M., Sukthankar, R.: An integer projected fixed point method for graph matching and MAP inference. In: Bengio, Y., Schuurmans, D., Lafferty, J.D., Williams, C.K.I., Culotta, A. (eds.) NIPS 2009. Curran Associates, pp. 1114\u20131122 (2009)"},{"key":"544_CR43","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/978-3-319-49055-7_43","volume-title":"Lecture Notes in Computer Science","author":"Julien Lerouge","year":"2016","unstructured":"Lerouge, J., Abu-Aisheh, Z., Raveaux, R., H\u00e9roux, P., Adam, S.: Exact graph edit distance computation using a binary linear program. In: Robles-Kelly, A., Loog, M., Biggio, B., Escolano, F., Wilson, R. (eds.) S+SSPR 2016, LNCS, vol. 10029. Springer, Cham, pp. 485\u2013495 (2016). \nhttps:\/\/doi.org\/10.1007\/978-3-319-49055-7_43"},{"key":"544_CR44","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/j.patcog.2017.07.029","volume":"72","author":"J Lerouge","year":"2017","unstructured":"Lerouge, J., Abu-Aisheh, Z., Raveaux, R., H\u00e9roux, P., Adam, S.: New binary linear programming formulation to compute the graph edit distance. Pattern Recognit. 72, 254\u2013265 (2017). \nhttps:\/\/doi.org\/10.1016\/j.patcog.2017.07.029","journal-title":"Pattern Recognit."},{"key":"544_CR45","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1007\/3-540-58325-4_168","volume-title":"Algorithms and Computation","author":"Chih-Long Lin","year":"1994","unstructured":"Lin, C.L.: Hardness of approximating graph transformation problem. In: Du, D.Z., Zhang, X.S. (eds.) Algorithms and Computation, LNCS, vol. 834. Springer, Berlin, pp. 74\u201382 (1994). \nhttps:\/\/doi.org\/10.1007\/3-540-58325-4_168"},{"issue":"1","key":"544_CR46","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1137\/0105003","volume":"5","author":"J Munkres","year":"1957","unstructured":"Munkres, J.: Algorithms for the assignment and transportation problems. SIAM J. Appl. Math. 5(1), 32\u201338 (1957). \nhttps:\/\/doi.org\/10.1137\/0105003","journal-title":"SIAM J. Appl. Math."},{"key":"544_CR47","unstructured":"Nissen, S.: Implementation of a Fast Artificial Neural Network Library (FANN). Technical report, Department of Computer Science, University of Copenhagen (2003). \nhttp:\/\/fann.sourceforge.net\/report\/"},{"issue":"2","key":"544_CR48","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1109\/TMI.2012.2230186","volume":"32","author":"E Ozdemir","year":"2013","unstructured":"Ozdemir, E., Gunduz-Demir, C.: A hybrid classification model for digital pathology using structural and statistical pattern recognition. IEEE Trans. Med. Imaging 32(2), 474\u2013483 (2013). \nhttps:\/\/doi.org\/10.1109\/TMI.2012.2230186","journal-title":"IEEE Trans. Med. Imaging"},{"key":"544_CR49","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-27252-8","volume-title":"Structural Pattern Recognition with Graph Edit Distance. Advances in Computer Vision and Pattern Recognition","author":"K Riesen","year":"2015","unstructured":"Riesen, K.: Structural Pattern Recognition with Graph Edit Distance. Advances in Computer Vision and Pattern Recognition. Springer, Cham (2015). \nhttps:\/\/doi.org\/10.1007\/978-3-319-27252-8"},{"key":"544_CR50","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/978-3-540-89689-0_33","volume-title":"Lecture Notes in Computer Science","author":"Kaspar Riesen","year":"2008","unstructured":"Riesen, K., Bunke, H.: IAM graph database repository for graph based pattern recognition and machine learning. In: da\u00a0Vitoria\u00a0Lobo, N., Kasparis, T., Roli, F., Kwok, J.T., Georgiopoulos, M., Anagnostopoulos, G.C., Loog, M. (eds.) S+SSPR 2008, LNCS, vol. 5342. Springer, Berlin, pp. 287\u2013297 (2008). \nhttps:\/\/doi.org\/10.1007\/978-3-540-89689-0_33"},{"issue":"7","key":"544_CR51","doi-asserted-by":"publisher","first-page":"950","DOI":"10.1016\/j.imavis.2008.04.004","volume":"27","author":"K Riesen","year":"2009","unstructured":"Riesen, K., Bunke, H.: Approximate graph edit distance computation by means of bipartite graph matching. Image Vis. Comput. 27(7), 950\u2013959 (2009). \nhttps:\/\/doi.org\/10.1016\/j.imavis.2008.04.004","journal-title":"Image Vis. Comput."},{"key":"544_CR52","doi-asserted-by":"publisher","DOI":"10.1142\/7731","volume-title":"Graph Classification and Clustering Based on Vector Space Embedding. Series in Machine Perception and Artificial Intelligence","author":"K Riesen","year":"2010","unstructured":"Riesen, K., Bunke, H.: Graph Classification and Clustering Based on Vector Space Embedding. Series in Machine Perception and Artificial Intelligence, vol. 77. World Scientific, Singapore (2010). \nhttps:\/\/doi.org\/10.1142\/7731"},{"key":"544_CR53","doi-asserted-by":"publisher","unstructured":"Riesen, K., Bunke, H., Fischer, A.: Improving graph edit distance approximation by centrality measures. In: ICPR 2014. IEEE Computer Society, pp. 3910\u20133914 (2014). \nhttps:\/\/doi.org\/10.1109\/ICPR.2014.671","DOI":"10.1109\/ICPR.2014.671"},{"key":"544_CR54","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1016\/j.patrec.2015.10.007","volume":"69","author":"K Riesen","year":"2016","unstructured":"Riesen, K., Ferrer, M.: Predicting the correctness of node assignments in bipartite graph matching. Pattern Recognit. Lett. 69, 8\u201314 (2016). \nhttps:\/\/doi.org\/10.1016\/j.patrec.2015.10.007","journal-title":"Pattern Recognit. Lett."},{"key":"544_CR55","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-319-18224-7_1","volume-title":"Graph-Based Representations in Pattern Recognition","author":"Kaspar Riesen","year":"2015","unstructured":"Riesen, K., Ferrer, M., Fischer, A., Bunke, H.: Approximation of graph edit distance in quadratic time. In: Liu, C., Luo, B., Kropatsch, W.G., Cheng, J. (eds.) GbRPR 2015, LNCS, vol. 9069. Springer, Cham, pp. 3\u201312 (2015). \nhttps:\/\/doi.org\/10.1007\/978-3-319-18224-7_1"},{"key":"544_CR56","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/978-3-319-11656-3_11","volume-title":"Advanced Information Systems Engineering","author":"Kaspar Riesen","year":"2014","unstructured":"Riesen, K., Fischer, A., Bunke, H.: Combining bipartite graph matching and beam search for graph edit distance approximation. In: Gayar, N.E., Schwenker, F., Suen, C. (eds.) ANNPR 2014, LNCS, vol. 8774. Springer, Cham, pp. 117\u2013128 (2014). \nhttps:\/\/doi.org\/10.1007\/978-3-319-11656-3_11"},{"key":"544_CR57","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11656-3","volume-title":"Artificial Neural Networks in Pattern Recognition","year":"2014","unstructured":"Riesen, K., Fischer, A., Bunke, H.: Computing upper and lower bounds of graph edit distance in cubic time. In: Gayar, N.E., Schwenker, F., Suen, C. (eds.) ANNPR 2014, LNCS, vol. 8774. Springer, Heidelberg, pp. 129\u2013140 (2014). \nhttps:\/\/doi.org\/10.1007\/978-3-319-11656-3"},{"key":"544_CR58","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1007\/978-3-319-58961-9_20","volume-title":"Graph-Based Representations in Pattern Recognition","author":"Kaspar Riesen","year":"2017","unstructured":"Riesen, K., Fischer, A., Bunke, H.: Improved graph edit distance approximation with simulated annealing. In: Foggia, P., Liu, C., Vento, M. (eds.) GbRPR 2017, LNCS, vol. 10310. Springer, Cham, pp. 222\u2013231 (2017). \nhttps:\/\/doi.org\/10.1007\/978-3-319-58961-9_20"},{"issue":"3","key":"544_CR59","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1109\/TSMC.1983.6313167","volume":"13","author":"A Sanfeliu","year":"1983","unstructured":"Sanfeliu, A., Fu, K.S.: A distance measure between attributed relational graphs for pattern recognition. IEEE Trans. Syst. Man Cybern. 13(3), 353\u2013362 (1983). \nhttps:\/\/doi.org\/10.1109\/TSMC.1983.6313167","journal-title":"IEEE Trans. Syst. Man Cybern."},{"issue":"Database\u2013Issue","key":"544_CR60","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1093\/nar\/gkh081","volume":"32","author":"I Schomburg","year":"2004","unstructured":"Schomburg, I., Chang, A., Ebeling, C., Gremse, M., Heldt, C., Huhn, G., Schomburg, D.: BRENDA, the enzyme database: updates and major new developments. Nucleic Acids Res. 32(Database\u2013Issue), 431\u2013433 (2004). \nhttps:\/\/doi.org\/10.1093\/nar\/gkh081","journal-title":"Nucleic Acids Res."},{"key":"544_CR61","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1007\/978-3-319-49055-7_49","volume-title":"Lecture Notes in Computer Science","author":"Michael Stauffer","year":"2016","unstructured":"Stauffer, M., Fischer, A., Riesen, K.: A novel graph database for handwritten word images. In: Robles-Kelly, A., Loog, M., Biggio, B., Escolano, F., Wilson, R. (eds.) S+SSPR 2016, LNCS, vol. 10029. Springer, Cham, pp. 553\u2013563 (2016). \nhttps:\/\/doi.org\/10.1007\/978-3-319-49055-7_49"},{"key":"544_CR62","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1007\/978-3-319-58961-9_22","volume-title":"Graph-Based Representations in Pattern Recognition","author":"Michael Stauffer","year":"2017","unstructured":"Stauffer, M., Tschachtli, T., Fischer, A., Riesen, K.: A survey on applications of bipartite graph edit distance. In: Foggia, P., Liu, C., Vento, M. (eds.) GbRPR 2017, LNCS, vol. 10310. Springer, Cham, pp. 242\u2013252 (2017). \nhttps:\/\/doi.org\/10.1007\/978-3-319-58961-9_22"},{"issue":"4","key":"544_CR63","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/BF02165411","volume":"13","author":"V Strassen","year":"1969","unstructured":"Strassen, V.: Gaussian elimination is not optimal. Numer. Math. 13(4), 354\u2013356 (1969). \nhttps:\/\/doi.org\/10.1007\/BF02165411","journal-title":"Numer. Math."},{"key":"544_CR64","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/3-540-63890-3_11","volume-title":"Algorithms and Computation","author":"Takeaki Uno","year":"1997","unstructured":"Uno, T.: Algorithms for enumerating all perfect, maximum and maximal matchings in bipartite graphs. In: Leong, H.W., Imai, H., Jain, S. (eds.) ISAAC 1997, LNCS, vol. 1350. Springer, Berlin, pp. 92\u2013101 (1997). \nhttps:\/\/doi.org\/10.1007\/3-540-63890-3_11"},{"key":"544_CR65","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/3-540-45678-3_32","volume-title":"Algorithms and Computation","author":"Takeaki Uno","year":"2001","unstructured":"Uno, T.: A fast algorithm for enumerating bipartite perfect matchings. In: Eades, P., Takaoka, T. (eds.) ISAAC 2001, LNCS, vol. 2223. Springer, Berlin, pp. 367\u2013379 (2001). \nhttps:\/\/doi.org\/10.1007\/3-540-45678-3_32"},{"issue":"2","key":"544_CR66","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/j.patcog.2014.01.002","volume":"48","author":"M Vento","year":"2015","unstructured":"Vento, M.: A long trip in the charming world of graphs for pattern recognition. Pattern Recognit. 48(2), 291\u2013301 (2015). \nhttps:\/\/doi.org\/10.1016\/j.patcog.2014.01.002","journal-title":"Pattern Recognit."},{"key":"544_CR67","doi-asserted-by":"publisher","unstructured":"Wang, X., Ding, X., Tung, A.K.H., Ying, S., Jin, H.: An efficient graph indexing method. In: Kementsietsidis, A., Salles, M.A.V. (eds.) ICDE 2012. IEEE Computer Society, pp. 210\u2013221 (2012). \nhttps:\/\/doi.org\/10.1109\/ICDE.2012.28","DOI":"10.1109\/ICDE.2012.28"},{"issue":"1","key":"544_CR68","doi-asserted-by":"publisher","first-page":"25","DOI":"10.14778\/1687627.1687631","volume":"2","author":"Z Zeng","year":"2009","unstructured":"Zeng, Z., Tung, A.K.H., Wang, J., Feng, J., Zhou, L.: Comparing stars: on approximating graph edit distance. PVLDB 2(1), 25\u201336 (2009). \nhttps:\/\/doi.org\/10.14778\/1687627.1687631","journal-title":"PVLDB"},{"issue":"1","key":"544_CR69","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/s00778-017-0487-0","volume":"27","author":"Xiang Zhao","year":"2017","unstructured":"Zhao, X., Xiao, C., Lin, X., Zhang, W., Wang, Y.: Efficient structure similarity searches: a partition-based approach. VLDB J. 27(1), 53\u201378 (2018). \nhttps:\/\/doi.org\/10.1007\/s00778-017-0487-0","journal-title":"The VLDB Journal"},{"key":"544_CR70","doi-asserted-by":"publisher","unstructured":"Zheng, W., Zou, L., Lian, X., Wang, D., Zhao, D.: Graph similarity search with edit distance constraint in large graph databases. In: He, Q., Iyengar, A., Nejdl, W., Pei, J., Rastogi, R. (eds.) CIKM 2013. ACM, pp. 1595\u20131600 (2013). \nhttps:\/\/doi.org\/10.1145\/2505515.2505723","DOI":"10.1145\/2505515.2505723"},{"issue":"4","key":"544_CR71","doi-asserted-by":"publisher","first-page":"964","DOI":"10.1109\/TKDE.2014.2349924","volume":"27","author":"W Zheng","year":"2015","unstructured":"Zheng, W., Zou, L., Lian, X., Wang, D., Zhao, D.: Efficient graph similarity search over large graph databases. IEEE Trans. Knowl. Data Eng. 27(4), 964\u2013978 (2015). \nhttps:\/\/doi.org\/10.1109\/TKDE.2014.2349924","journal-title":"IEEE Trans. Knowl. Data Eng."}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-019-00544-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00778-019-00544-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-019-00544-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,13]],"date-time":"2020-07-13T23:13:48Z","timestamp":1594682028000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00778-019-00544-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,15]]},"references-count":71,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["544"],"URL":"https:\/\/doi.org\/10.1007\/s00778-019-00544-1","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,15]]},"assertion":[{"value":"31 December 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 May 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 May 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 July 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}