{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T21:57:21Z","timestamp":1725573441152},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540309352"},{"type":"electronic","value":"9783540324263"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11602613_42","type":"book-chapter","created":{"date-parts":[[2005,12,2]],"date-time":"2005-12-02T08:24:24Z","timestamp":1133511864000},"page":"412-421","source":"Crossref","is-referenced-by-count":2,"title":["Improved Algorithms for Largest Cardinality 2-Interval Pattern Problem"],"prefix":"10.1007","author":[{"given":"Hao","family":"Yuan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Linji","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erdong","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"42_CR1","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)"},{"issue":"2-3","key":"42_CR2","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"},{"key":"42_CR3","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/978-3-540-30219-3_4","volume-title":"Algorithms in Bioinformatics","author":"J. Gramm","year":"2004","unstructured":"Gramm, J.: A polynomial-time algorithm for the matching of crossing contact-map patterns. In: Jonassen, I., Kim, J. (eds.) WABI 2004. LNCS (LNBI), vol.\u00a03240, pp. 38\u201349. Springer, Heidelberg (2004)"},{"issue":"2-3","key":"42_CR4","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/j.tcs.2003.10.026","volume":"312","author":"J. Alber","year":"2004","unstructured":"Alber, J., Gramm, J., Guo, J., Niedermeier, R.: Computing the similarity of two sequences with nested arc annotations. Theoretical Computer Science\u00a0312(2-3), 337\u2013358 (2004)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"42_CR5","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S1570-8667(03)00080-7","volume":"2","author":"T. Jiang","year":"2004","unstructured":"Jiang, T., Lin, G., Ma, B., Zhang, K.: The longest common subsequence problem for arc-annotated sequences. J. Discrete Algorithms\u00a02(2), 257\u2013270 (2004)","journal-title":"J. Discrete Algorithms"},{"key":"42_CR6","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":"42_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/978-3-540-27801-6_23","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, pp. 311\u2013322. Springer, Heidelberg (2004)"},{"key":"42_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11561071_1","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. 1\u20138. Springer, Heidelberg (2005)"},{"key":"42_CR9","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(\\sqrt{|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":"42_CR10","unstructured":"Bar-Yehuda, R., Halld\u00f3rsson, 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)"},{"issue":"1","key":"42_CR11","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 Mathematics\u00a074(1), 13\u201332 (1997)","journal-title":"Discrete Applied Mathematics"},{"key":"42_CR12","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1002\/net.3230200203","volume":"20","author":"S. Masuda","year":"1990","unstructured":"Masuda, S., Nakajima, K., Kashiwabara, T., Fujisawa, T.: Efficient algorithms for finding maximum cliques of an overlap graph. Networks\u00a020, 157\u2013171 (1990)","journal-title":"Networks"},{"key":"42_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/978-3-540-24587-2_15","volume-title":"Algorithms and Computation","author":"G. Valiente","year":"2003","unstructured":"Valiente, G.: A new simple algorithm for the maximum-weight independent set problem on circle graphs. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol.\u00a02906, pp. 129\u2013137. Springer, Heidelberg (2003)"},{"key":"42_CR14","doi-asserted-by":"crossref","unstructured":"Hopcroft, J.E., Karp, R.M.: An n 5\/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing\u00a0(4) (1973)","DOI":"10.1137\/0202019"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11602613_42.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:02:51Z","timestamp":1619506971000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11602613_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540309352","9783540324263"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/11602613_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}