{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T12:22:15Z","timestamp":1742991735151,"version":"3.40.3"},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319193144"},{"type":"electronic","value":"9783319193151"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-19315-1_18","type":"book-chapter","created":{"date-parts":[[2015,6,6]],"date-time":"2015-06-06T10:42:08Z","timestamp":1433587328000},"page":"200-212","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On Maximum Common Subgraph Problems in Series-Parallel Graphs"],"prefix":"10.1007","author":[{"given":"Nils","family":"Kriege","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florian","family":"Kurpicz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petra","family":"Mutzel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,7]]},"reference":[{"issue":"9","key":"18_CR1","first-page":"1488","volume":"E76\u2013A","author":"T Akutsu","year":"1993","unstructured":"Akutsu, T.: A polynomial time algorithm for finding a largest common subgraph of almost trees of bounded degree. IEICE Trans. Fundam. E76\u2013A(9), 1488\u20131493 (1993)","journal-title":"IEICE Trans. Fundam."},{"key":"18_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/978-3-642-35261-4_18","volume-title":"Algorithms and Computation","author":"T Akutsu","year":"2012","unstructured":"Akutsu, T., Tamura, T.: On the complexity of the maximum common subgraph problem for partial k-trees of bounded degree. In: Chao, K.-M., Hsu, T., Lee, D.-T. (eds.) ISAAC 2012. LNCS, vol. 7676, pp. 146\u2013155. Springer, Heidelberg (2012)"},{"issue":"1","key":"18_CR3","doi-asserted-by":"publisher","first-page":"119","DOI":"10.3390\/a6010119","volume":"6","author":"T Akutsu","year":"2013","unstructured":"Akutsu, T., Tamura, T.: A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree. Algorithms 6(1), 119\u2013135 (2013)","journal-title":"Algorithms"},{"key":"18_CR4","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. Society for Industrial and Applied Mathematics, Philadelphia (1999)"},{"key":"18_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/978-3-642-22006-7_11","volume-title":"Automata, Languages and Programming","author":"M Chimani","year":"2011","unstructured":"Chimani, M., Hlin\u011bn\u00fd, P.: A tighter insertion-based approximation of the crossing number. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol. 6755, pp. 122\u2013134. Springer, Heidelberg (2011)"},{"key":"18_CR6","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. WH Freeman and Company, New York (1979)"},{"key":"18_CR7","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithm Theory - SWAT \u201994","author":"A Gupta","year":"1994","unstructured":"Gupta, A., Nishimura, N.: Sequential and parallel algorithms for embedding problems on classes of partial $$k$$-trees. In: Schmidt, E.M., Skyum, S. (eds.) SWAT 1994. LNCS, vol. 824. Springer, Heidelberg (1994)"},{"issue":"1\u20132","key":"18_CR8","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0304-3975(96)00046-1","volume":"164","author":"A Gupta","year":"1996","unstructured":"Gupta, A., Nishimura, N.: The complexity of subgraph isomorphism for classes of partial $$k$$-trees. Theoret. Comput. Sci. 164(1\u20132), 287\u2013298 (1996)","journal-title":"Theoret. Comput. Sci."},{"issue":"3133","key":"18_CR9","doi-asserted-by":"publisher","first-page":"2784","DOI":"10.1016\/j.tcs.2010.03.030","volume":"411","author":"T Horvth","year":"2010","unstructured":"Horvth, T., Ramon, J.: Efficient frequent connected subgraph mining in graphs of bounded tree-width. Theoret. Comput. Sci. 411(3133), 2784\u20132797 (2010)","journal-title":"Theoret. Comput. Sci."},{"key":"18_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1007\/978-3-662-44465-8_43","volume-title":"Mathematical Foundations of Computer Science 2014","author":"N Kriege","year":"2014","unstructured":"Kriege, N., Mutzel, P.: Finding maximum common biconnected subgraphs in series-parallel graphs. In: Csuhaj-Varj\u00fa, E., Dietzfelbinger, M., \u00c9sik, Z. (eds.) MFCS 2014, Part II. LNCS, vol. 8635, pp. 505\u2013516. Springer, Heidelberg (2014)"},{"issue":"1\u20132","key":"18_CR11","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. Naval Res. Logistics Q. 2(1\u20132), 83\u201397 (1955)","journal-title":"Naval Res. Logistics Q."},{"key":"18_CR12","unstructured":"Kurpicz, F.: Efficient algorithms for the maximum common subgraph problem in partial 2-trees. Master\u2019s thesis, TU Dortmund (2014)"},{"issue":"1\u20133","key":"18_CR13","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0012-365X(92)90687-B","volume":"108","author":"J Matouek","year":"1992","unstructured":"Matouek, J., Thomas, R.: On the complexity of finding iso- and other morphisms for partial k-trees. Discrete Math. 108(1\u20133), 343\u2013364 (1992)","journal-title":"Discrete Math."},{"key":"18_CR14","doi-asserted-by":"crossref","unstructured":"Matula, D.W.: Subtree isomorphism in $$O(n^{5\/2})$$. In: Algorithmic Aspects of Combinatorics, Ann. Discrete Math., vol. 2, pp. 91\u2013106 (1978)","DOI":"10.1016\/S0167-5060(08)70324-8"},{"issue":"1","key":"18_CR15","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0166-218X(01)00223-2","volume":"115","author":"T Nishizeki","year":"2001","unstructured":"Nishizeki, T., Vygen, J., Zhou, X.: The edge-disjoint paths problem is np-complete for series-parallel graphs. Discrete Appl. Math. 115(1), 177\u2013186 (2001)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"18_CR16","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/s10994-010-5193-8","volume":"83","author":"L Schietgat","year":"2011","unstructured":"Schietgat, L., Costa, F., Ramon, J., De Raedt, L.: Effective feature construction by maximum common subgraph sampling. Mach. Learn. 83(2), 137\u2013161 (2011)","journal-title":"Mach. Learn."},{"key":"18_CR17","unstructured":"Schietgat, L., Ramon, J., Bruynooghe, M.: A polynomial-time metric for outerplanar graphs. In: Mining and Learning with Graphs (MLG) (2007)"},{"key":"18_CR18","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/978-3-540-88411-8_20","volume-title":"Discovery Science","author":"L Schietgat","year":"2008","unstructured":"Schietgat, L., Ramon, J., Bruynooghe, M., Blockeel, H.: An efficiently computable graph-based metric for the classification of small molecules. In: Boulicaut, J.-F., Berthold, M.R., Horv\u00e1th, T. (eds.) DS 2008. LNCS (LNAI), vol. 5255, pp. 197\u2013209. Springer, Heidelberg (2008)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-19315-1_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,16]],"date-time":"2023-02-16T21:48:53Z","timestamp":1676584133000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-19315-1_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319193144","9783319193151"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-19315-1_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"7 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}