{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:19:55Z","timestamp":1740097195713,"version":"3.37.3"},"publisher-location":"Cham","reference-count":42,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319210230"},{"type":"electronic","value":"9783319210247"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-21024-7_1","type":"book-chapter","created":{"date-parts":[[2015,6,30]],"date-time":"2015-06-30T09:17:17Z","timestamp":1435655837000},"page":"3-16","source":"Crossref","is-referenced-by-count":10,"title":["Greedy Graph Edit Distance"],"prefix":"10.1007","author":[{"given":"Kaspar","family":"Riesen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miquel","family":"Ferrer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Dornberger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Horst","family":"Bunke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,7,1]]},"reference":[{"key":"1_CR1","series-title":"Lecture Notes in Computer Science","volume-title":"Machine Learning and Data Mining in Pattern Recognition","year":"2012","unstructured":"Perner, P. (ed.): MLDM 2012. LNCS, vol. 7376. Springer, Heidelberg (2012)"},{"key":"1_CR2","series-title":"Lecture Notes in Computer Science","volume-title":"Machine Learning and Data Mining in Pattern Recognition","year":"2013","unstructured":"Perner, P. (ed.): MLDM 2013. LNCS, vol. 7988. Springer, Heidelberg (2013)"},{"key":"1_CR3","volume-title":"Pattern Classification","author":"RO Duda","year":"2000","unstructured":"Duda, R.O., Hart, P.E., Stork, D.G.: Pattern Classification, 2nd edn. Wiley-Interscience, New York (2000)","edition":"2"},{"key":"1_CR4","volume-title":"Pattern Recognition and Machine Learning","author":"C Bishop","year":"2008","unstructured":"Bishop, C.: Pattern Recognition and Machine Learning. Springer, New York (2008)"},{"key":"1_CR5","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511809682","volume-title":"Kernel Methods for Pattern Analysis","author":"J Shawe-Taylor","year":"2004","unstructured":"Shawe-Taylor, J., Cristianini, N.: Kernel Methods for Pattern Analysis. Cambridge University Press, Cambridge (2004)"},{"issue":"3","key":"1_CR6","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 Recogn. Artif. Intell. 18(3), 265\u2013298 (2004)","journal-title":"Int. J. Pattern Recogn. Artif. Intell."},{"doi-asserted-by":"crossref","unstructured":"Foggia, P., Percannella, G., Vento, M.: Graph matching and learning in pattern recognition in the last 10 years. Int. J. Pattern Recogn. Artif. Intell. 28(1) (2014). \n                      http:\/\/dx.doi.org\/10.1142\/S0218001414500013","key":"1_CR7","DOI":"10.1142\/S0218001414500013"},{"volume-title":"Mining Graph Data","year":"2007","unstructured":"Cook, D., Holder, L. (eds.): Mining Graph Data. Wiley-Interscience, New York (2007)","key":"1_CR8"},{"key":"1_CR9","doi-asserted-by":"crossref","DOI":"10.1142\/5832","volume-title":"Graph-Theoretic Techniques for Web Content Mining","author":"A Schenker","year":"2005","unstructured":"Schenker, A., Bunke, H., Last, M., Kandel, A.: Graph-Theoretic Techniques for Web Content Mining. World Scientific Publishing, Singapore (2005)"},{"key":"1_CR10","doi-asserted-by":"crossref","DOI":"10.1142\/6855","volume-title":"Kernels for Structured Data","author":"T G\u00e4rtner","year":"2008","unstructured":"G\u00e4rtner, T.: Kernels for Structured Data. World Scientific Publishng, Singapore (2008)"},{"key":"1_CR11","first-page":"467","volume-title":"Encyclopedia of Machine Learning","author":"T G\u00e4rtner","year":"2010","unstructured":"G\u00e4rtner, T., Horvath, T., Wrobel, S.: Graph kernels. In: Smmut, C., Webb, G.I. (eds.) Encyclopedia of Machine Learning, pp. 467\u2013469. Springer US, London (2010)"},{"key":"1_CR12","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 Recogn. Lett. 1, 245\u2013253 (1983)","journal-title":"Pattern Recogn. Lett."},{"issue":"3","key":"1_CR13","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.: A distance measure between attributed relational graphs for pattern recognition. IEEE Trans. Syst. Man Cybern. (Part B) 13(3), 353\u2013363 (1983)","journal-title":"IEEE Trans. Syst. Man Cybern. (Part B)"},{"key":"1_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1007\/978-3-642-34166-3_11","volume-title":"Structural and Syntactic Pattern Recognition","author":"X Cort\u00e9s","year":"2012","unstructured":"Cort\u00e9s, X., Serratosa, F., Sol\u00e9, A.: Active graph matching based on pairwise probabilities between nodes. In: Gimelfarb, G., Hancock, E., Imiya, A., Kuijper, A., Kudo, M. (eds.) SSPR 2012. LNCS, vol. 7626, pp. 98\u2013106. Springer, Heidelberg (2012)"},{"key":"1_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/978-3-540-24838-5_8","volume-title":"Efficient and Experimental Algorithms","author":"M Boeres","year":"2004","unstructured":"Boeres, M., Ribeiro, C., Bloch, I.: A randomized heuristic for scene recognition by graph matching. In: Ribeiro, C., Martins, S. (eds.) WEA 2004. LNCS, vol. 3059, pp. 100\u2013113. Springer, Heidelberg (2004)"},{"key":"1_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/978-3-540-31988-7_16","volume-title":"Graph-based Representations in Pattern Recognition","author":"S Sorlin","year":"2005","unstructured":"Sorlin, S., Solnon, C.: Reactive tabu search for measuring graph similarity. In: Brun, L., Vento, M. (eds.) GbRPR 2005. LNCS, vol. 3434, pp. 172\u2013182. Springer, Heidelberg (2005)"},{"key":"1_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/978-3-540-27868-9_18","volume-title":"Structural, Syntactic, and Statistical Pattern Recognition","author":"M Neuhaus","year":"2004","unstructured":"Neuhaus, M., Bunke, H.: An error-tolerant approximate matching algorithm for attributed planar graphs and its application to fingerprint classification. In: Fred, A., Caelli, T.M., Duin, R.P.W., Campilho, A.C. (eds.) SSPR 2004. LNCS, vol. 3138, pp. 180\u2013189. Springer, Heidelberg (2004)"},{"issue":"8","key":"1_CR18","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)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"1_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/3-540-45028-9_2","volume-title":"Graph Based Representations in Pattern Recognition","author":"P Dickinson","year":"2003","unstructured":"Dickinson, P., Bunke, H., Dadej, A., Kraetzl, M.: On graphs with unique node labels. In: Hancock, E., Vento, M. (eds.) GbRPR 2003. LNCS, vol. 2726, pp. 13\u201323. Springer, Heidelberg (2003)"},{"issue":"4","key":"1_CR20","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(4), 950\u2013959 (2009)","journal-title":"Image Vis. Comput."},{"key":"1_CR21","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898717754","volume-title":"Assignment Problems","author":"R Burkard","year":"2009","unstructured":"Burkard, R., Dell\u2019Amico, M., Martello, S.: Assignment Problems. Society for Industrial and Applied Mathematics, Philadelphia (2009)"},{"issue":"6","key":"1_CR22","doi-asserted-by":"publisher","first-page":"1048","DOI":"10.1109\/TPAMI.2009.28","volume":"31","author":"TS Caetano","year":"2009","unstructured":"Caetano, T.S., McAuley, J.J., Cheng, L., Le, Q.V., Smola, A.J.: Learning graph matching. IEEE Trans. Pattern Anal. Mach. Intell. 31(6), 1048\u20131058 (2009)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"2","key":"1_CR23","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"P Hart","year":"1968","unstructured":"Hart, P., Nilsson, N., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100\u2013107 (1968)","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"unstructured":"Riesen, K., Fischer, A., Bunke, H.: Computing upper and lower bounds of graph edit distance in cubic time. Accepted for publication in Proceedings of the IAPR TC3 International Workshop on Artificial Neural Networks in Pattern Recognition","key":"1_CR24"},{"issue":"1","key":"1_CR25","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. J. Soc. Ind. Appl. Math. 5(1), 32\u201338 (1957)","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"1_CR26","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"H Kuhn","year":"1955","unstructured":"Kuhn, H.: The hungarian method for the assignment problem. Naval Res. Logistic Q. 2, 83\u201397 (1955)","journal-title":"Naval Res. Logistic Q."},{"key":"1_CR27","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/BF02278710","volume":"38","author":"R Jonker","year":"1987","unstructured":"Jonker, R., Volgenant, A.: A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing 38, 325\u2013340 (1987)","journal-title":"Computing"},{"key":"1_CR28","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0167-6377(86)90073-8","volume":"5","author":"R Jonker","year":"1986","unstructured":"Jonker, R., Volgenant, A.: Improving the hungarian assignment algorithm. Oper. Res. Lett. 5, 171\u2013175 (1986)","journal-title":"Oper. Res. Lett."},{"key":"1_CR29","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02186476","volume":"14","author":"D Bertsekas","year":"1988","unstructured":"Bertsekas, D.: The auction algorithm: a distributed relaxation method for the assignment problem. Ann. Oper. Res. 14, 105\u2013123 (1988)","journal-title":"Ann. Oper. Res."},{"key":"1_CR30","doi-asserted-by":"publisher","first-page":"969","DOI":"10.1287\/opre.28.4.969","volume":"28","author":"M Hung","year":"1983","unstructured":"Hung, M.: A polynomial simplex method for the assignment problem. Oper. Res. 28, 969\u2013982 (1983)","journal-title":"Oper. Res."},{"key":"1_CR31","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1007\/BFb0121050","volume":"24","author":"J Orlin","year":"1985","unstructured":"Orlin, J.: On the simplex algorithm for networks and generalized networks. Math. Program. Stud. 24, 166\u2013178 (1985)","journal-title":"Math. Program. Stud."},{"issue":"1","key":"1_CR32","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1287\/opre.40.1.S5","volume":"40","author":"R Ahuja","year":"1992","unstructured":"Ahuja, R., Orlin, J.: The scaling network simplex algorithm. Oper. Res. 40(1), 5\u201313 (1992)","journal-title":"Oper. Res."},{"key":"1_CR33","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0167-6377(88)90082-X","volume":"7","author":"M Akg\u00fcl","year":"1988","unstructured":"Akg\u00fcl, M.: A sequential dual simplex algorithm for the linear assignment problem. Oper. Res. Lett. 7, 155\u2013518 (1988)","journal-title":"Oper. Res. Lett."},{"key":"1_CR34","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1007\/BF01593805","volume":"12","author":"V Srinivasan","year":"1977","unstructured":"Srinivasan, V., Thompson, G.: Cost operator algorithms for the transportation problem. Math. Program. 12, 372\u2013391 (1977)","journal-title":"Math. Program."},{"key":"1_CR35","first-page":"1","volume":"4","author":"H Achatz","year":"1991","unstructured":"Achatz, H., Kleinschmidt, P., Paparrizos, K.: A dual forest algorithm for the assignment problem. Appl. Geom. Discret. Math. AMS 4, 1\u201311 (1991)","journal-title":"Appl. Geom. Discret. Math. AMS"},{"unstructured":"Burkard, R., Ceia, E.: Linear assignment problems and extensions. Technical report 127, Karl-Franzens-Universit\u00e4t Graz und Technische Universit\u00e4t Graz (1998)","key":"1_CR36"},{"key":"1_CR37","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1002\/net.3230130404","volume":"13","author":"D Avis","year":"1983","unstructured":"Avis, D.: A survey of heuristics for the weighted matching problem. Networks 13, 475\u2013493 (1983)","journal-title":"Networks"},{"issue":"4","key":"1_CR38","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1145\/321138.321140","volume":"9","author":"J Kurtzberg","year":"1962","unstructured":"Kurtzberg, J.: On approximation methods for the assignment problem. J. ACM 9(4), 419\u2013439 (1962)","journal-title":"J. ACM"},{"issue":"6","key":"1_CR39","doi-asserted-by":"publisher","first-page":"1053","DOI":"10.1142\/S021800140900748X","volume":"23","author":"K Riesen","year":"2008","unstructured":"Riesen, K., Bunke, H.: Graph classification based on vector space embedding. Int. J. Pattern Recogn. Artif. Intell. 23(6), 1053\u20131081 (2008)","journal-title":"Int. J. Pattern Recogn. Artif. Intell."},{"key":"1_CR40","doi-asserted-by":"crossref","DOI":"10.1142\/6523","volume-title":"Bridging the Gap Between Graph Edit Distance and Kernel Machines","author":"M Neuhaus","year":"2007","unstructured":"Neuhaus, M., Bunke, H.: Bridging the Gap Between Graph Edit Distance and Kernel Machines. World Scientific Publishing, Singapore (2007)"},{"key":"1_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/978-3-540-89689-0_33","volume-title":"Structural, Syntactic, and Statistical Pattern Recognition","author":"K Riesen","year":"2008","unstructured":"Riesen, K., Bunke, H.: IAM graph database repository for graph based pattern recognition and machine learning. In: da Vitoria Lobo, N., et al. (eds.) Structural, Syntactic, and Statistical Pattern Recognition. LNCS, vol. 5342, pp. 287\u2013297. Springer, Heidelberg (2008)"},{"key":"1_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/11767978_35","volume-title":"Graphics Recognition. Ten yearsreview and future perspectives","author":"P Dosch","year":"2005","unstructured":"Dosch, P., Valveny, E.: Report on the second symbol recognition contest. In: Wenyin, L., Llad\u00f3s, J. (eds.) GREC 2005. LNCS, vol. 3926, pp. 381\u2013397. Springer, Heidelberg (2005)"}],"container-title":["Lecture Notes in Computer Science","Machine Learning and Data Mining in Pattern Recognition"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21024-7_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,10,6]],"date-time":"2018-10-06T01:29:29Z","timestamp":1538789369000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-21024-7_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319210230","9783319210247"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21024-7_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}