{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,13]],"date-time":"2023-09-13T18:37:25Z","timestamp":1694630245078},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,8,3]],"date-time":"2007-08-03T00:00:00Z","timestamp":1186099200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2007,8,3]],"date-time":"2007-08-03T00:00:00Z","timestamp":1186099200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2008,7]]},"DOI":"10.1007\/s10878-007-9097-x","type":"journal-article","created":{"date-parts":[[2007,8,2]],"date-time":"2007-08-02T04:33:53Z","timestamp":1186029233000},"page":"39-49","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Parameterized lower bound and inapproximability of\u00a0polylogarithmic string barcoding"],"prefix":"10.1007","volume":"16","author":[{"given":"Chunmei","family":"Liu","sequence":"first","affiliation":[]},{"given":"Yinglei","family":"Song","sequence":"additional","affiliation":[]},{"given":"Legand L.","family":"Burge","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,8,3]]},"reference":[{"key":"9097_CR1","doi-asserted-by":"crossref","unstructured":"Berman P, DasGupta B, Sontag E (2004) Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks. In: Proceedings of the seventh international workshop on approximation algorithms for combinatorial optimization problems, pp 39\u201350","DOI":"10.1007\/978-3-540-27821-4_4"},{"issue":"2","key":"9097_CR2","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/j.jcss.2005.02.001","volume":"71","author":"P Berman","year":"2005","unstructured":"Berman P, DasGupta B, Kao MY (2005) Tight approximability results for test set problems in bioinformatics. J\u00a0Comput Syst Sci 71(2):145\u2013162","journal-title":"J\u00a0Comput Syst Sci"},{"key":"9097_CR3","first-page":"1","volume":"1","author":"J Borneman","year":"2001","unstructured":"Borneman J, Chrobak M, Vedova GD, Figueora A, Jiang T (2001) Probe selection algorithms with applications in the analysis of microbial communities. Bioinformatics 1:1\u20139","journal-title":"Bioinformatics"},{"key":"9097_CR4","unstructured":"Cazalis D, Milledge T, Narasimhan G (2004) Probe selection problem: structure and algorithms. In: Proceedings of the eighth multi-conference on systemics, cybernetics and informatics, pp 124\u2013129"},{"key":"9097_CR5","doi-asserted-by":"crossref","unstructured":"DasGupta B, Konwar K, Mandoiu II, Shvartsman A (2005) Highly scalable algorithms for robust string barcoding. In: Proceedings of international conference on computational science, vol\u00a02, pp 1020\u20131028","DOI":"10.1007\/11428848_129"},{"key":"9097_CR6","doi-asserted-by":"crossref","unstructured":"Dinur I, Safra S (2002) The importance of being biased. In: Proceedings of the 34th annual ACM symposium on theory of computing, pp 33\u201342","DOI":"10.1145\/509907.509915"},{"key":"9097_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"RG Downey","year":"1999","unstructured":"Downey RG, Fellows MR (1999) Parameterized complexity. Springer, Berlin"},{"key":"9097_CR8","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, New York"},{"issue":"1","key":"9097_CR9","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1145\/6462.6502","volume":"18","author":"Z Gavil","year":"1986","unstructured":"Gavil Z (1986) Efficient algorithms for finding maximum matchings in graphs. ACM Comput Surv 18(1):23\u201328","journal-title":"ACM Comput Surv"},{"key":"9097_CR10","doi-asserted-by":"crossref","unstructured":"Rash S, Gusfield D (2002) String barcoding: uncovering optimal virus signatures. In: Proceedings of the sixth annual international conference on research in computational biology, pp 254\u2013261","DOI":"10.1145\/565196.565229"},{"key":"9097_CR11","doi-asserted-by":"crossref","unstructured":"Raz R, Safra S (1997) A sub-constant error-probability low-degree test, and sub-constant error-probability PCP characterization of NP. In: Proceedings of the 29th annual ACM symposium on theory of computing, pp 475\u2013484","DOI":"10.1145\/258533.258641"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-007-9097-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-007-9097-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-007-9097-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-007-9097-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,29]],"date-time":"2022-07-29T02:10:22Z","timestamp":1659060622000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-007-9097-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,8,3]]},"references-count":11,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,7]]}},"alternative-id":["9097"],"URL":"https:\/\/doi.org\/10.1007\/s10878-007-9097-x","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,8,3]]},"assertion":[{"value":"3 August 2007","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}