{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,19]],"date-time":"2026-01-19T01:30:28Z","timestamp":1768786228136,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540735557","type":"print"},{"value":"9783540735564","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73556-4_39","type":"book-chapter","created":{"date-parts":[[2007,8,28]],"date-time":"2007-08-28T15:55:47Z","timestamp":1188316547000},"page":"378-387","source":"Crossref","is-referenced-by-count":8,"title":["A PTAS for the Weighted 2-Interval Pattern Problem over the Preceding-and-Crossing Model"],"prefix":"10.1007","author":[{"given":"Minghui","family":"Jiang","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"1-3","key":"39_CR1","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0166-218X(00)00186-4","volume":"104","author":"T. Akutsu","year":"2000","unstructured":"Akutsu, T.: Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots. Discrete Applied Mathematics\u00a0104(1-3), 45\u201362 (2000)","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"39_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0097539703437843","volume":"36","author":"R. Bar-Yehuda","year":"2006","unstructured":"Bar-Yehuda, R., Halld\u00f3rsson, M.M., Naor, J(S.), Shachnai, H., Shapira, I.: Scheduling split intervals. SIAM Journal on Computing\u00a036(1), 1\u201315 (2006), Preliminary version In: Proceedings of the 13th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), pp. 732\u2013741 (2002)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"39_CR3","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/s10878-006-9020-x","volume":"13","author":"S. Bereg","year":"2007","unstructured":"Bereg, S., Kubica, M., Wale\u0144, T., Zhu, B.: RNA multiple structural alignment with longest common subsequences. Journal of Combinatorial Optimization\u00a013(2), 179\u2013188 (2007)","journal-title":"Journal of Combinatorial Optimization"},{"key":"39_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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)"},{"issue":"3","key":"39_CR5","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/s10878-006-9030-8","volume":"13","author":"E. Chen","year":"2007","unstructured":"Chen, E., Yang, L., Yuan, H.: Improved algorithms for largest cardinality 2-interval pattern problem. Journal of Combinatorial Optimization, Special Issue on Bioinformatics\u00a013(3), 263\u2013275 (2007)","journal-title":"Journal of Combinatorial Optimization, Special Issue on Bioinformatics"},{"key":"39_CR6","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":"39_CR7","unstructured":"Crochemore, M., Hermelin, D., Landau, G.M., Rawitz, D., Vialette, S.: Approximating the 2-interval pattern problem. Theoretical Computer Science (to appear)"},{"issue":"6","key":"39_CR8","doi-asserted-by":"crossref","first-page":"981","DOI":"10.1089\/106652703322756186","volume":"10","author":"S. Ieong","year":"2003","unstructured":"Ieong, S., Kao, M.-Y., Lam, T.-W., Sung, W.-K., Yiu, S.-M.: Predicting RNA secondary structure with arbitrary pseudoknots by maximizing the number of stacking pairs. Journal of Computational Biology\u00a010(6), 981\u2013995 (2003), (Preliminary version In: Proceedings of the 2nd Annual IEEE International Symposium on Bioinformatics and Bioengineering (BIBE 2001), pp. 183\u2013190 (2001)","journal-title":"Journal of Computational Biology"},{"issue":"3","key":"39_CR9","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/s10878-006-9024-6","volume":"13","author":"M. Jiang","year":"2007","unstructured":"Jiang, M.: A 2-approximation for the preceding-and-crossing structured 2-interval pattern problem. Journal of Combinatorial Optimization, Special Issue on Bioinformatics\u00a013(3), 217\u2013221 (2007)","journal-title":"Journal of Combinatorial Optimization, Special Issue on Bioinformatics"},{"key":"39_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/978-3-540-72870-2_38","volume-title":"AAIM 2007","author":"M. Jiang","year":"2007","unstructured":"Jiang, M.: Improved approximation algorithms for predicting RNA secondary structures with arbitrary pseudoknots. In: AAIM 2007. Proceedings of the 3rd International Conference on Algorithmic Aspects in Information and Management. LNCS, vol.\u00a04508, pp. 399\u2013410. Springer, Heidelberg (2007)"},{"key":"39_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"919","DOI":"10.1007\/978-3-540-27836-8_77","volume-title":"Automata, Languages and Programming","author":"R.B. Lyngs\u00f8","year":"2004","unstructured":"Lyngs\u00f8, R.B.: Complexity of pseudoknot prediction in simple models. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 919\u2013931. Springer, Heidelberg (2004)"},{"issue":"3\/4","key":"39_CR12","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1089\/106652700750050862","volume":"7","author":"R.B. Lyngs\u00f8","year":"2000","unstructured":"Lyngs\u00f8, R.B., Pedersen, C.N.S.: RNA pseudoknot prediction in energy-based models. Journal of Computational Biology\u00a07(3\/4), 409\u2013427 (2000)","journal-title":"Journal of Computational Biology"},{"key":"39_CR13","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An \n                    \n                      \n                    \n                    $O(\\sqrt{|V|} |E|)$\n                   algorithm for finding maximum matching in general graphs. In: Proceedings of the 21st Annual Symposium on Foundations of Computer Science (FOCS 1980), pp. 17\u201327 (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"39_CR14","unstructured":"Vialette, S.: On the computational complexity of 2-interval pattern matching problems. Theoretical Computer Science 312, pp. 223\u2013249 (2004), (Preliminary version in Proceedings of the 13th Annual Symposium on Combinatorial Pattern Matching (CPM 2002), LNCS 2373, pp. 53\u201363, 2002)"},{"key":"39_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1007\/11602613_42","volume-title":"Algorithms and Computation","author":"H. Yuan","year":"2005","unstructured":"Yuan, H., Yang, L., Chen, E.: Improved algorithms for largest cardinality 2-interval pattern problem. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol.\u00a03827, pp. 412\u2013421. Springer, Heidelberg (2005)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73556-4_39.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T09:51:46Z","timestamp":1619517106000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73556-4_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540735557","9783540735564"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73556-4_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}