{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T22:48:29Z","timestamp":1768776509305,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540223412","type":"print"},{"value":"9783540278016","type":"electronic"}],"license":[{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"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":[[2004]]},"DOI":"10.1007\/978-3-540-27801-6_23","type":"book-chapter","created":{"date-parts":[[2010,9,5]],"date-time":"2010-09-05T23:00:15Z","timestamp":1283727615000},"page":"311-322","source":"Crossref","is-referenced-by-count":12,"title":["New Results for the 2-Interval Pattern Problem"],"prefix":"10.1007","author":[{"given":"Guillaume","family":"Blin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guillaume","family":"Fertin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"St\u00e9phane","family":"Vialette","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"23_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/3-540-45452-7_10","volume-title":"Combinatorial Pattern Matching","author":"J. Alber","year":"2002","unstructured":"Alber, J., Gramm, J., Guo, J., Niedermeier, R.: Towards optimally solving the longest common subsequence problem for sequences with nested arc annotations in linear time. In: Apostolico, A., Takeda, M. (eds.) CPM 2002. LNCS, vol.\u00a02373, pp. 99\u2013114. Springer, Heidelberg (2002)"},{"key":"23_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-1-4613-8369-7_1","volume":"56","author":"J.R.S. Blair","year":"1993","unstructured":"Blair, J.R.S., Peyton, B.: An introduction to chordal graphs and clique trees. Graph Theory and Sparse Matrix Computation\u00a056, 1\u201329 (1993)","journal-title":"Graph Theory and Sparse Matrix Computation"},{"key":"23_CR3","unstructured":"Bar-Yehuda, R., Halldorsson, M.M., Naor, J., Shachnai, H., Shapira, I.: Scheduling split intervals. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 732\u2013741 (2002)"},{"key":"23_CR4","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0166-218X(88)90032-7","volume":"21","author":"I. Dagan","year":"1988","unstructured":"Dagan, I., Golumbic, M.C., Pinter, R.Y.: Trapezoid graphs and their coloring. Discrete Applied Mathematics\u00a021, 35\u201346 (1988)","journal-title":"Discrete Applied Mathematics"},{"key":"23_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/3-540-48452-3_20","volume-title":"Combinatorial Pattern Matching","author":"P.A. Evans","year":"1999","unstructured":"Evans, P.A.: Finding common subsequences with arcs and pseudoknots. In: Crochemore, M., Paterson, M. (eds.) CPM 1999. LNCS, vol.\u00a01645, pp. 270\u2013280. Springer, Heidelberg (1999)"},{"key":"23_CR6","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D.R. Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pacific Journal of Math.\u00a015, 835\u2013855 (1965)","journal-title":"Pacific Journal of Math."},{"key":"23_CR7","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/S0166-218X(96)00013-3","volume":"74","author":"S. Felsner","year":"1997","unstructured":"Felsner, S., M\u00fcller, R., Wernisch, L.: Trapezoid graphs and generalizations: Geometry and algorithms. Discrete Applied Math.\u00a074, 13\u201332 (1997)","journal-title":"Discrete Applied Math."},{"key":"23_CR8","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0012-365X(75)90103-X","volume":"11","author":"M.L. Fredman","year":"1975","unstructured":"Fredman, M.L.: On computing the length of longest increasing subsequences. Disrete Mathematics\u00a011, 29\u201335 (1975)","journal-title":"Disrete Mathematics"},{"key":"23_CR9","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 arcannotated sequences. In: Agrawal, M., Seth, A.K. (eds.) FSTTCS 2002. LNCS, vol.\u00a02556, pp. 182\u2013193. Springer, Heidelberg (2002)"},{"key":"23_CR10","doi-asserted-by":"crossref","unstructured":"Goldman, D., Istrail, S., Papadimitriou, C.H.: Algorithmic aspects of protein structure similarity. In: Proceedings of the 40th Annual Symposium of Foundations of Computer Science (FOCS 1999), pp. 512\u2013522 (1999)","DOI":"10.1109\/SFFCS.1999.814624"},{"key":"23_CR11","volume-title":"Algorithmic graph theory and perfect graphs","author":"M.C. Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic graph theory and perfect graphs. Academic Press, New York (1980)"},{"key":"23_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0601001","volume":"1","author":"J.R. Griggs","year":"1979","unstructured":"Griggs, J.R., West, D.B.: Extremal values of the interval number of a graph, I. SIAM J. Alg. Discrete Methods\u00a01, 1\u20137 (1979)","journal-title":"SIAM J. Alg. Discrete Methods"},{"key":"23_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/3-540-45123-4_15","volume-title":"Combinatorial Pattern Matching","author":"T. Jiang","year":"2000","unstructured":"Jiang, T., Lin, G.-H., Ma, B., Zhang, K.: The longest common subsequence problem for arc-annotated sequences. In: Giancarlo, R., Sankoff, D. (eds.) CPM 2000. LNCS, vol.\u00a01848, pp. 154\u2013165. Springer, Heidelberg (2000)"},{"key":"23_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1007\/3-540-55706-7_29","volume-title":"Algorithm Theory - SWAT \u201992","author":"D. Joseph","year":"1992","unstructured":"Joseph, D., Meidanis, J., Tiwari, P.: Determining DNA sequence similarity using maximum independent set algorithms for interval graphs. In: Nurmi, O., Ukkonen, E. (eds.) SWAT 1992. LNCS, vol.\u00a0621, pp. 326\u2013337. Springer, Heidelberg (1992)"},{"key":"23_CR15","first-page":"17","volume-title":"Proceedings of the 21st Annual Symposium on Foundation of Computer Science","author":"S. Micali","year":"1980","unstructured":"Micali, S., Vazirani, V.V.: An O(_|V ||E|) algorithm for finding maximum matching in general graphs. In: Proceedings of the 21st Annual Symposium on Foundation of Computer Science, pp. 17\u201327. IEEE, Los Alamitos (1980)"},{"key":"23_CR16","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1002\/jgt.3190030302","volume":"3","author":"W.T. Trotter","year":"1979","unstructured":"Trotter, W.T., Harary, F.: On double and multiple interval graphs. J. Graph Theory\u00a03, 205\u2013211 (1979)","journal-title":"J. Graph Theory"},{"key":"23_CR17","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"R.E. Tarjan","year":"1984","unstructured":"Tarjan, R.E.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput.\u00a013, 566\u2013579 (1984)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"23_CR18","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF01305952","volume":"14","author":"V.V. Vazirani","year":"1994","unstructured":"Vazirani, V.V.: A theory of alternating paths and blossoms for proving correctness of the O(_|V ||E|) maximum matching algorithm. Combinatorica\u00a014(1), 71\u2013109 (1994)","journal-title":"Combinatorica"},{"key":"23_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1007\/3-540-44696-6_8","volume-title":"Algorithms in Bioinformatics","author":"J. Viksna","year":"2001","unstructured":"Viksna, J., Gilbert, D.: Pattern matching and pattern discovery algorithms for protein topologies. In: Gascuel, O., Moret, B.M.E. (eds.) WABI 2001. LNCS, vol.\u00a02149, pp. 98\u2013111. Springer, Heidelberg (2001)"},{"key":"23_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/3-540-45452-7_6","volume-title":"Combinatorial Pattern Matching","author":"S. Vialette","year":"2002","unstructured":"Vialette, S.: Pattern matching problems over 2-interval sets. In: Apostolico, A., Takeda, M. (eds.) CPM 2002. LNCS, vol.\u00a02373, pp. 53\u201363. Springer, Heidelberg (2002)"},{"issue":"2-3","key":"23_CR21","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. Theoretical Computer Science\u00a0312(2-3), 223\u2013249 (2004)","journal-title":"Theoretical Computer Science"},{"key":"23_CR22","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0166-218X(84)90127-6","volume":"8","author":"D.B. West","year":"1984","unstructured":"West, D.B., Shmoys, D.B.: Recognizing graphs with fixed interval number is NP-complete. Discrete Applied Mathematics\u00a08, 295\u2013305 (1984)","journal-title":"Discrete Applied Mathematics"}],"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-27801-6_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T15:50:44Z","timestamp":1740498644000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27801-6_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540223412","9783540278016"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27801-6_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}