{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T03:20:54Z","timestamp":1725679254203},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642301902"},{"type":"electronic","value":"9783642301919"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-30191-9_2","type":"book-chapter","created":{"date-parts":[[2012,5,9]],"date-time":"2012-05-09T14:08:08Z","timestamp":1336572488000},"page":"13-23","source":"Crossref","is-referenced-by-count":4,"title":["Inapproximability of (1,2)-Exemplar Distance"],"prefix":"10.1007","author":[{"given":"Laurent","family":"Bulteau","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Minghui","family":"Jiang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"2_CR1","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P. Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theoretical Computer Science\u00a0237, 123\u2013134 (2000)","journal-title":"Theoretical Computer Science"},{"key":"2_CR2","doi-asserted-by":"crossref","first-page":"19","DOI":"10.7155\/jgaa.00175","volume":"13","author":"S. Angibaud","year":"2009","unstructured":"Angibaud, S., Fertin, G., Rusu, I., Th\u00e9venin, A., Vialette, S.: On the approximability of comparing genomes with duplicates. Journal of Graph Algorithms and Applications\u00a013, 19\u201353 (2009)","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"2_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/3-540-48523-6_17","volume-title":"Automata, Languages and Programming","author":"P. Berman","year":"1999","unstructured":"Berman, P., Karpinski, M.: On Some Tighter Inapproximability Results. In: Wiedermann, J., van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol.\u00a01644, pp. 200\u2013209. Springer, Heidelberg (1999)"},{"key":"2_CR4","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1109\/TCBB.2007.1069","volume":"4","author":"G. Blin","year":"2007","unstructured":"Blin, G., Chauve, C., Fertin, G., Rizzi, R., Vialette, S.: Comparing genomes with duplications: a computational complexity point of view. IEEE\/ACM Transactions on Computational Biology and Bioinformatics\u00a04, 523\u2013534 (2007)","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"key":"2_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/978-3-642-00202-1_31","volume-title":"WALCOM: Algorithms and Computation","author":"G. Blin","year":"2009","unstructured":"Blin, G., Fertin, G., Sikora, F., Vialette, S.: The Exemplar\n                Breakpoint\n                Distance for Non-trivial Genomes Cannot Be Approximated. In: Das, S., Uehara, R. (eds.) WALCOM 2009. LNCS, vol.\u00a05431, pp. 357\u2013368. Springer, Heidelberg (2009)"},{"key":"2_CR6","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1109\/TCBB.2007.1066","volume":"4","author":"P. Bonizzoni","year":"2007","unstructured":"Bonizzoni, P., Della Vedova, G., Dondi, R., Fertin, G., Rizzi, R., Vialette, S.: Exemplar longest common subsequence. IEEE\/ACM Transactions on Computational Biology and Bioinformatics\u00a04, 535\u2013543 (2007)","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"key":"2_CR7","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s10878-007-9077-1","volume":"15","author":"Z. Chen","year":"2008","unstructured":"Chen, Z., Fowler, R.H., Fu, B., Zhu, B.: On the inapproximability of the exemplar conserved interval distance problem of genomes. Journal of Combinatorial Optimization\u00a015, 201\u2013221 (2008); A preliminary version appeared in Proceedings of the 12th Annual International Conference on Computing and Combinatorics, COCOON 2006, pp. 245\u2013254 (2006)","journal-title":"Journal of Combinatorial Optimization"},{"key":"2_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/11775096_27","volume-title":"Algorithmic Aspects in Information and Management","author":"Z. Chen","year":"2006","unstructured":"Chen, Z., Fu, B., Zhu, B.: The Approximability of the Exemplar Breakpoint Distance Problem. In: Cheng, S.-W., Poon, C.K. (eds.) AAIM 2006. LNCS, vol.\u00a04041, pp. 291\u2013302. Springer, Heidelberg (2006)"},{"key":"2_CR9","doi-asserted-by":"publisher","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I. Dinur","year":"2005","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Annals of Mathematics\u00a0162, 439\u2013485 (2005)","journal-title":"Annals of Mathematics"},{"key":"2_CR10","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company (1979)"},{"key":"2_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/300515.300516","volume":"46","author":"S. Hannenhalli","year":"1999","unstructured":"Hannenhalli, S., Pevzner, P.: Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. Journal of the ACM\u00a046, 1\u201327 (1999)","journal-title":"Journal of the ACM"},{"key":"2_CR12","doi-asserted-by":"publisher","first-page":"1077","DOI":"10.1089\/cmb.2011.0097","volume":"18","author":"M. Jiang","year":"2011","unstructured":"Jiang, M.: The zero exemplar distance problem. Journal of Computational Biology\u00a018, 1077\u20131086 (2011)","journal-title":"Journal of Computational Biology"},{"key":"2_CR13","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S. Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2\u2009\u2212\u2009\u03b5. Journal of Computer and System Sciences\u00a074, 335\u2013349 (2008)","journal-title":"Journal of Computer and System Sciences"},{"key":"2_CR14","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1093\/bioinformatics\/15.11.909","volume":"15","author":"D. Sankoff","year":"1999","unstructured":"Sankoff, D.: Genome rearrangement with gene families. Bioinformatics\u00a015, 909\u2013917 (1999)","journal-title":"Bioinformatics"},{"key":"2_CR15","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/11554714_11","volume-title":"Comparative Genomics","author":"D. Sankoff","year":"2005","unstructured":"Sankoff, D., Haque, L.: Power Boosts for Cluster Tests. In: McLysaght, A., Huson, D.H. (eds.) RECOMB 2005. LNCS (LNBI), vol.\u00a03678, pp. 121\u2013130. Springer, Heidelberg (2005)"}],"container-title":["Lecture Notes in Computer Science","Bioinformatics Research and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-30191-9_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:30:59Z","timestamp":1620127859000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-30191-9_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642301902","9783642301919"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-30191-9_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}