{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,19]],"date-time":"2026-01-19T01:52:00Z","timestamp":1768787520241,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540438625","type":"print"},{"value":"9783540454526","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45452-7_6","type":"book-chapter","created":{"date-parts":[[2007,5,15]],"date-time":"2007-05-15T21:55:29Z","timestamp":1179266129000},"page":"53-63","source":"Crossref","is-referenced-by-count":6,"title":["Pattern Matching Problems over 2-Interval Sets"],"prefix":"10.1007","author":[{"given":"St\u00e9phane","family":"Vialette","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,6,21]]},"reference":[{"key":"6_CR1","doi-asserted-by":"publisher","first-page":"1395","DOI":"10.1093\/nar\/24.8.1395","volume":"24","author":"B. Billoud","year":"1996","unstructured":"B. Billoud, M. Kontic, and A. Viari. Palingol: a declarative programming language to describe nucleic acids secondary structures and to scan sequence database. Nucl. Acids Res., 24:1395\u2013403, 1996.","journal-title":"Nucl. Acids Res."},{"key":"6_CR2","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0166-218X(88)90032-7","volume":"21","author":"I. Dagan","year":"1988","unstructured":"I. Dagan, M. C. Golumbic, and R. Y. Pinter. Trapezoid graphs and their coloring. Discrete Appl. Math., 21:35\u201346, 1988.","journal-title":"Discrete Appl. Math."},{"key":"6_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/3-540-48452-3_20","volume-title":"Proceedings of the 10th Annual Symposium Combinatorial Pattern Matching (CPM 1999)","author":"P. Evans","year":"1999","unstructured":"P. Evans. Finding common subsequences with arcs and pseudoknots. In Proceedings of the 10th Annual Symposium Combinatorial Pattern Matching (CPM 1999), volume 1645 of Lecture Notes in Computer Science, pages 270\u2013280, 1999."},{"key":"6_CR4","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/S0166-218X(96)00013-3","volume":"74","author":"S. Felsner","year":"1997","unstructured":"S. Felsner, R. M\u00fcller, and L. Wernisch. Trapezoid graphs and generalizations: Geometry and algorithms. Discrete Appl. Math., 74:13\u201332, 1997.","journal-title":"Discrete Appl. Math."},{"key":"6_CR5","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman, San Franciso, 1979."},{"key":"6_CR6","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1002\/net.3230030305","volume":"3","author":"F. Gavril","year":"1973","unstructured":"F. Gavril. Algorithms for a maximum clique and a minimum independent set of a circle graph. Networks, 3:261\u2013273, 1973.","journal-title":"Networks"},{"key":"6_CR7","doi-asserted-by":"crossref","unstructured":"D. Goldman, S. Istrail, and C. H. Papadimitriou. Algorithmic aspects of protein structure similarity. In IEEE Proceedings of the 40th Annual Conference of Foundations of Computer Science (FOCS99), pages 512\u2013521, 1999.","DOI":"10.1109\/SFFCS.1999.814624"},{"key":"6_CR8","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M. C. Golumbic","year":"1980","unstructured":"M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980."},{"key":"6_CR9","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1002\/net.3230120410","volume":"12","author":"U. I. Gupta","year":"1982","unstructured":"U. I. Gupta, D. T. Lee, and J.Y-T. Leung. Efficient algorithms for interval graph and circular-arc graphs. Networks, 12:459\u2013467, 1982.","journal-title":"Networks"},{"key":"6_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/3-540-45123-4_15","volume-title":"Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching (CPM 2000)","author":"T. Jiang","year":"2000","unstructured":"T. Jiang, G.-H. Lin, B. Ma, and K. Zhang. The longest common subsequence problem for arc-annotated sequences. In Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching (CPM 2000), volume 1848 of Lecture Notes in Computer Science, pages 154\u2013165, 2000."},{"key":"6_CR11","series-title":"PhD thesis","volume-title":"Tree matching problems with applications to structured text databases","author":"P. Kilpel\u00e4inen","year":"1992","unstructured":"P. Kilpel\u00e4inen. Tree matching problems with applications to structured text databases. PhD thesis, University of Helsinki, Finland, 1992."},{"key":"6_CR12","doi-asserted-by":"publisher","first-page":"699","DOI":"10.1287\/opre.14.4.699","volume":"14","author":"E. L. Lawler","year":"1966","unstructured":"E. L. Lawler and D. W. Wood. Branch and bound methods: A survey. Operations Research, 14:699\u2013719, 1966.","journal-title":"Operations Research"},{"key":"6_CR13","series-title":"PhD thesis","volume-title":"Aspects algorithmiques de la pr\u2019ediction des structures secondaires d\u2019ARN","author":"S. Vialette","year":"2001","unstructured":"S. Vialette. Aspects algorithmiques de la pr\u2019ediction des structures secondaires d\u2019ARN. PhD thesis, Universit\u2019e Denis Diderot, Paris, France, 2001. (in french)."},{"key":"6_CR14","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0166-218X(84)90127-6","volume":"8","author":"D. B. West","year":"1984","unstructured":"D. B. West and D. B. Shmoys. Recognizing graphs with fixed interval number is NP-complete. Discrete Appl. Math., 8:295\u2013305, 1984.","journal-title":"Discrete Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45452-7_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,16]],"date-time":"2019-02-16T12:44:58Z","timestamp":1550321098000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45452-7_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540438625","9783540454526"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-45452-7_6","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2002]]}}}