{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T09:40:21Z","timestamp":1737366021167,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540734369"},{"type":"electronic","value":"9783540734376"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-73437-6_25","type":"book-chapter","created":{"date-parts":[[2007,8,13]],"date-time":"2007-08-13T17:36:44Z","timestamp":1187026604000},"page":"241-252","source":"Crossref","is-referenced-by-count":1,"title":["Common Structured Patterns in Linear Graphs: Approximation and Combinatorics"],"prefix":"10.1007","author":[{"given":"Guillaume","family":"Fertin","sequence":"first","affiliation":[]},{"given":"Danny","family":"Hermelin","sequence":"additional","affiliation":[]},{"given":"Romeo","family":"Rizzi","sequence":"additional","affiliation":[]},{"given":"St\u00e9phane","family":"Vialette","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"25_CR1","unstructured":"Alon, N.: Private communication (2006)"},{"key":"25_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/3-540-57182-5_13","volume-title":"Mathematical Foundations of Computer Science 1993","author":"L. Alonso","year":"1993","unstructured":"Alonso, L., Schott, R.: On the tree inclusion problem. In: Borzyszkowski, A.M., Sokolowski, S. (eds.) MFCS 1993. LNCS, vol.\u00a0711, pp. 211\u2013221. Springer, Heidelberg (1993)"},{"key":"25_CR3","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/BF01840365","volume":"2","author":"A. Apostolico","year":"1987","unstructured":"Apostolico, A., Guerra, C.: The longest common subsequence problem revisited. Algorithmica\u00a02, 315\u2013336 (1987)","journal-title":"Algorithmica"},{"key":"25_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"860","DOI":"10.1007\/11428848_110","volume-title":"Computational Science \u2013 ICCS 2005","author":"G. Blin","year":"2005","unstructured":"Blin, G., Fertin, G., Rizzi, R., Vialette, S.: What makes the arc-preserving subsequence problem hard\u00a0? In: Sunderam, V.S., van Albada, G.D., Sloot, P.M.A., Dongarra, J.J. (eds.) ICCS 2005. LNCS, vol.\u00a03515, pp. 860\u2013868. Springer, Heidelberg (2005)"},{"key":"25_CR5","series-title":"Lecture Notes in Computer Science","volume-title":"Combinatorial Pattern Matching","author":"G. Blin","year":"2004","unstructured":"Blin, G., Fertin, G., Vialette, S.: New results for the 2-interval pattern problem. In: Sahinalp, S.C., Muthukrishnan, S.M., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol.\u00a03109, Springer, Heidelberg (2004)"},{"issue":"5","key":"25_CR6","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/S0020-0190(97)00209-3","volume":"65","author":"P. Bose","year":"1998","unstructured":"Bose, P., Buss, J.F., Lubiw, A.: Pattern matching for permutations. IPL\u00a065(5), 277\u2013283 (1998)","journal-title":"IPL"},{"issue":"6","key":"25_CR7","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0020-0190(92)90114-B","volume":"43","author":"M.-S. Chang","year":"1992","unstructured":"Chang, M.-S., Wang, F.-G.: Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs. IPL\u00a043(6), 293\u2013295 (1992)","journal-title":"IPL"},{"issue":"2","key":"25_CR8","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1006\/jagm.1997.0899","volume":"26","author":"W. Chen","year":"1998","unstructured":"Chen, W.: More efficient algorithm for ordered tree inclusion. J. Algorithms\u00a026(2), 370\u2013385 (1998)","journal-title":"J. Algorithms"},{"key":"25_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1007\/11561071_39","volume-title":"Algorithms \u2013 ESA 2005","author":"M. Crochemore","year":"2005","unstructured":"Crochemore, M., Hermelin, D., Landau, G.M., Vialette, S.: Approximating the 2-interval pattern problem. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 426\u2013437. Springer, Heidelberg (2005)"},{"key":"25_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1007\/978-3-540-27801-6_19","volume-title":"Combinatorial Pattern Matching","author":"E. Davydov","year":"2004","unstructured":"Davydov, E., Batzoglou, S.: A computational model for RNA multiple structural alignment. In: Sahinalp, S.C., Muthukrishnan, S.M., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol.\u00a03109, pp. 254\u2013269. Springer, Heidelberg (2004)"},{"key":"25_CR11","doi-asserted-by":"crossref","first-page":"161","DOI":"10.2307\/1969503","volume":"51","author":"R.P. Dilworth","year":"1950","unstructured":"Dilworth, R.P.: A decomposition theorem for partially ordered sets. Annals of Mathematics Series 2\u00a051, 161\u2013166 (1950)","journal-title":"Annals of Mathematics Series 2"},{"issue":"3","key":"25_CR12","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1145\/146637.146650","volume":"39","author":"D. Eppstein","year":"1992","unstructured":"Eppstein, D., Galil, Z., Giancarlo, R., Italiano, G.F.: Sparse dynamic programming I: Linear cost functions. J. ACM\u00a039(3), 519\u2013545 (1992)","journal-title":"J. ACM"},{"key":"25_CR13","first-page":"463","volume":"2","author":"P. Erd\u0151s","year":"1935","unstructured":"Erd\u0151s, P., Szekeres, G.: A combinatorial problem in geometry. Compositio Mathematica\u00a02, 463\u2013470 (1935)","journal-title":"Compositio Mathematica"},{"key":"25_CR14","unstructured":"Evans, P.A.: Algorithms and complexity for annotated sequence analysis. PhD thesis, University of Alberta (1999)"},{"key":"25_CR15","doi-asserted-by":"crossref","unstructured":"Goldman, D., Istrail, S., Papadimitriou, C.H.: Algorithmic aspects of protein structure similarity. In: Proc. 40th Foundations of Computer Science (FOCS), pp. 512\u2013522 (1999)","DOI":"10.1109\/SFFCS.1999.814624"},{"issue":"4","key":"25_CR16","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1109\/TCBB.2004.35","volume":"1","author":"J. Gramm","year":"2004","unstructured":"Gramm, J.: A polynomial-time algorithm for the matching of crossing contact-map patterns. IEEE\/ACM Trans. Comp. Biol. and Bioinfo.\u00a01(4), 171\u2013180 (2004)","journal-title":"IEEE\/ACM Trans. Comp. Biol. and Bioinfo."},{"key":"25_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/3-540-36206-1_17","volume-title":"FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science","author":"J. Gramm","year":"2002","unstructured":"Gramm, J., Guo, J., Niedermeier, R.: Pattern matching for arc-annotated sequences. In: Agrawal, M., Seth, A.K. (eds.) FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science. LNCS, vol.\u00a02556, pp. 182\u2013193. Springer, Heidelberg (2002)"},{"key":"25_CR18","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1002\/net.3230120410","volume":"12","author":"U.I. Gupta","year":"1982","unstructured":"Gupta, U.I., Lee, D.T., Leung, J.Y.-T.: Efficient algorithms for interval graph and circular-arc graphs. Networks\u00a012, 459\u2013467 (1982)","journal-title":"Networks"},{"issue":"4","key":"25_CR19","doi-asserted-by":"publisher","first-page":"664","DOI":"10.1145\/322033.322044","volume":"24","author":"D.S. Hirschberg","year":"1977","unstructured":"Hirschberg, D.S.: Algorithms for the longest common subsequence problem. J. ACM\u00a024(4), 664\u2013675 (1977)","journal-title":"J. ACM"},{"key":"25_CR20","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1145\/359581.359603","volume":"20","author":"J.W. Hunt","year":"1977","unstructured":"Hunt, J.W., Szymanski, T.G.: A fast algorithm for computing longest common subsequences. Communications of the ACM\u00a020, 350\u2013353 (1977)","journal-title":"Communications of the ACM"},{"issue":"2","key":"25_CR21","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1137\/S0097539791218202","volume":"24","author":"P. Kilpel\u00e4inen","year":"1995","unstructured":"Kilpel\u00e4inen, P., Mannila, H.: Ordered and unordered tree inclusion. SIAM J. Comp.\u00a024(2), 340\u2013356 (1995)","journal-title":"SIAM J. Comp."},{"key":"25_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/3-540-68530-8_8","volume-title":"Algorithms - ESA \u201998","author":"P.N. Klein","year":"1998","unstructured":"Klein, P.N.: Computing the edit-distance between unrooted ordered trees. In: Bilardi, G., Pietracaprina, A., Italiano, G.F., Pucci, G. (eds.) ESA 1998. LNCS, vol.\u00a01461, pp. 91\u2013102. Springer, Heidelberg (1998)"},{"key":"25_CR23","first-page":"204","volume":"10","author":"A. Kostochka","year":"1988","unstructured":"Kostochka, A.: On upper bounds on the chromatic numbers of graphs. Transactions of the Institute of Mathematics (Siberian Branch of the Academy of Sciences in USSR)\u00a010, 204\u2013226 (1988)","journal-title":"Transactions of the Institute of Mathematics (Siberian Branch of the Academy of Sciences in USSR)"},{"key":"25_CR24","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/S0012-365X(96)00344-5","volume":"163","author":"A. Kostochka","year":"1997","unstructured":"Kostochka, A., Kratochvil, J.: Covering and coloring polygon-circle graphs. Discrete Mathematics\u00a0163, 299\u2013305 (1997)","journal-title":"Discrete Mathematics"},{"key":"25_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/11780441_20","volume-title":"Combinatorial Pattern Matching","author":"M. Kubica","year":"2006","unstructured":"Kubica, M., Rizzi, R., Vialette, S., Wale\u0144, T.: Approximation of RNA multiple structural alignment. In: Lewenstein, M., Valiente, G. (eds.) CPM 2006. LNCS, vol.\u00a04009, pp. 211\u2013222. Springer, Heidelberg (2006)"},{"key":"25_CR26","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/11851561_22","volume-title":"Algorithms in Bioinformatics","author":"S.C. Li","year":"2006","unstructured":"Li, S.C., Li, M.: On the complexity of the crossing contact map pattern matching problem. In: B\u00fccher, P., Moret, B.M.E. (eds.) WABI 2006. LNCS (LNBI), vol.\u00a04175, pp. 231\u2013241. Springer, Heidelberg (2006)"},{"issue":"2","key":"25_CR27","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D. Maier","year":"1978","unstructured":"Maier, D.: The complexity of some problems on subsequences and supersequences. J. ACM\u00a025(2), 322\u2013336 (1978)","journal-title":"J. ACM"},{"issue":"1","key":"25_CR28","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/0022-0000(80)90002-1","volume":"20","author":"W.J. Masek","year":"1980","unstructured":"Masek, W.J., Paterson, M.S.: A faster algorithm computing string edit distances. J. Comp. and Syst. Sc.\u00a020(1), 18\u201331 (1980)","journal-title":"J. Comp. and Syst. Sc."},{"issue":"6","key":"25_CR29","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1137\/0218082","volume":"18","author":"D. Shasha","year":"1989","unstructured":"Shasha, D., Zhang, K.: Simple fast algorithms for the editing distance between trees and related problems. SIAM J. Comp.\u00a018(6), 1245\u20131262 (1989)","journal-title":"SIAM J. Comp."},{"key":"25_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/11780441_25","volume-title":"Combinatorial Pattern Matching","author":"A. Tiskin","year":"2006","unstructured":"Tiskin, A.: Longest common subsequences in permutations and maximum cliques in circle graphs. In: Lewenstein, M., Valiente, G. (eds.) CPM 2006. LNCS, vol.\u00a04009, pp. 270\u2013281. Springer, Heidelberg (2006)"},{"issue":"2-3","key":"25_CR31","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/j.tcs.2003.08.010","volume":"312","author":"S. Vialette","year":"2004","unstructured":"Vialette, S.: On the computational complexity of 2-interval pattern matching problems. Theoretical Computer Science\u00a0312(2-3), 223\u2013249 (2004)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73437-6_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T09:25:10Z","timestamp":1737365110000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73437-6_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540734369","9783540734376"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73437-6_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}