{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:33:06Z","timestamp":1725557586949},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642135088"},{"type":"electronic","value":"9783642135095"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13509-5_12","type":"book-chapter","created":{"date-parts":[[2010,6,22]],"date-time":"2010-06-22T09:19:57Z","timestamp":1277198397000},"page":"125-137","source":"Crossref","is-referenced-by-count":5,"title":["On the Parameterized Complexity of Some Optimization Problems Related to Multiple-Interval Graphs"],"prefix":"10.1007","author":[{"given":"Minghui","family":"Jiang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1016\/j.dam.2005.01.001","volume":"155","author":"L. Alc\u00f3n","year":"2007","unstructured":"Alc\u00f3n, L., Cerioli, M.R., de Figueiredo, C.M.H., Gutierrez, M., Meidanis, J.: Tree loop graphs. Discrete Applied Mathematics\u00a0155, 686\u2013694 (2007)","journal-title":"Discrete Applied Mathematics"},{"key":"12_CR2","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0166-218X(96)00063-7","volume":"71","author":"V. Bafna","year":"1996","unstructured":"Bafna, V., Narayanan, B., Ravi, R.: Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles). Discrete Applied Mathematics\u00a071, 41\u201353 (1996)","journal-title":"Discrete Applied Mathematics"},{"key":"12_CR3","doi-asserted-by":"publisher","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\u201315 (2006)","journal-title":"SIAM Journal on Computing"},{"key":"12_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"710","DOI":"10.1007\/978-3-642-10631-6_72","volume-title":"Algorithms and Computation","author":"L. Bulteau","year":"2009","unstructured":"Bulteau, L., Fertin, G., Rusu, I.: Maximal strip recovery problem with gaps: hardness and approximation algorithms. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol.\u00a05878, pp. 710\u2013719. Springer, Heidelberg (2009)"},{"key":"12_CR5","unstructured":"Butman, A., Hermelin, D., Lewenstein, M., Rawitz, D.: Optimization problems in multiple-interval graphs. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pp. 268\u2013277 (2007)"},{"key":"12_CR6","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/s10878-009-9233-x","volume":"18","author":"Z. Chen","year":"2009","unstructured":"Chen, Z., Fu, B., Jiang, M., Zhu, B.: On recovering syntenic blocks from comparative maps. Journal of Combinatorial Optimization\u00a018, 307\u2013318 (2009)","journal-title":"Journal of Combinatorial Optimization"},{"key":"12_CR7","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/j.tcs.2008.01.007","volume":"395","author":"M. Crochemore","year":"2008","unstructured":"Crochemore, M., Hermelin, D., Landau, G.M., Rawitz, D., Vialette, S.: Approximating the 2-interval pattern problem. Theoretical Computer Science\u00a0395, 283\u2013297 (2008)","journal-title":"Theoretical Computer Science"},{"key":"12_CR8","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1998","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1998)"},{"key":"12_CR9","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"M.R. Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theoretical Computer Science\u00a0410, 53\u201361 (2009)","journal-title":"Theoretical Computer Science"},{"key":"12_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-540-74839-7_6","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"P. Gambette","year":"2007","unstructured":"Gambette, P., Vialette, S.: On restrictions of balanced 2-interval graphs. In: Brandst\u00e4dt, A., Kratsch, D., M\u00fcller, H. (eds.) WG 2007. LNCS, vol.\u00a04769, pp. 55\u201365. Springer, Heidelberg (2007)"},{"key":"12_CR11","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0012-365X(79)90183-3","volume":"28","author":"J.R. Griggs","year":"1979","unstructured":"Griggs, J.R.: Extremal values of the interval number of a graph, II. Discrete Mathematics\u00a028, 37\u201347 (1979)","journal-title":"Discrete Mathematics"},{"key":"12_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0601001","volume":"1","author":"J.R. Griggs","year":"1980","unstructured":"Griggs, J.R., West, D.B.: Extremal values of the interval number of a graph. SIAM Journal on Algebraic and Discrete Methods\u00a01, 1\u20137 (1980)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"12_CR13","first-page":"109","volume":"109","author":"A. Gy\u00e1rf\u00e1s","year":"1995","unstructured":"Gy\u00e1rf\u00e1s, A., West, D.B.: Multitrack interval graphs. Congressus Numerantium\u00a0109, 109\u2013116 (1995)","journal-title":"Congressus Numerantium"},{"key":"12_CR14","doi-asserted-by":"crossref","unstructured":"Jiang, M.: Approximation algorithms for predicting RNA secondary structures with arbitrary pseudoknots. IEEE\/ACM Transactions on Computational Biology and Bioinformatics, doi:10.1109\/TCBB.2008.109 (to appear)","DOI":"10.1109\/TCBB.2008.109"},{"key":"12_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1007\/978-3-642-10631-6_63","volume-title":"Algorithms and Computation","author":"M. Jiang","year":"2009","unstructured":"Jiang, M.: Inapproximability of maximal strip recovery. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol.\u00a05878, pp. 616\u2013625. Springer, Heidelberg (2009)"},{"key":"12_CR16","unstructured":"Jiang, M.: Inapproximability of maximal strip recovery: II (Submitted)"},{"key":"12_CR17","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":"12_CR18","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1002\/jgt.3190030302","volume":"3","author":"W.T. Trotter Jr.","year":"1979","unstructured":"Trotter Jr., W.T., Harary, F.: On double and multiple interval graphs. Journal of Graph Theory\u00a03, 205\u2013211 (1979)","journal-title":"Journal of Graph Theory"},{"key":"12_CR19","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, 223\u2013249 (2004)","journal-title":"Theoretical Computer Science"},{"key":"12_CR20","doi-asserted-by":"crossref","unstructured":"Wang, L., Zhu, B.: On the tractability of maximal strip recovery. In: Proceedings of the 6th Annual Conference on Theory and Applications of Models of Computation (TAMC 2009), pp. 400\u2013409 (2009)","DOI":"10.1007\/978-3-642-02017-9_42"},{"key":"12_CR21","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"},{"key":"12_CR22","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1109\/TCBB.2007.1075","volume":"4","author":"C. Zheng","year":"2007","unstructured":"Zheng, C., Zhu, Q., Sankoff, D.: Removing noise and ambiguities from comparative maps in rearrangement analysis. IEEE\/ACM Transactions on Computational Biology and Bioinformatics\u00a04, 515\u2013522 (2007)","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13509-5_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T12:05:52Z","timestamp":1619784352000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13509-5_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642135088","9783642135095"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13509-5_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}