{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T09:03:16Z","timestamp":1787389396342,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540343813","type":"print"},{"value":"9783540343820","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11758525_102","type":"book-chapter","created":{"date-parts":[[2006,5,11]],"date-time":"2006-05-11T15:03:32Z","timestamp":1147359812000},"page":"758-766","source":"Crossref","is-referenced-by-count":17,"title":["Minimum Multicolored Subgraph Problem in Multiplex PCR Primer Set Selection and Population Haplotyping"],"prefix":"10.1007","author":[{"given":"M. T.","family":"Hajiaghayi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"K.","family":"Jain","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"L. C.","family":"Lau","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"I. I.","family":"M\u0103ndoiu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"A.","family":"Russell","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"V. V.","family":"Vazirani","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"102_CR1","doi-asserted-by":"crossref","first-page":"S128","DOI":"10.1093\/bioinformatics\/18.suppl_1.S128","volume":"18","author":"R. Fernandes","year":"2002","unstructured":"Fernandes, R., Skiena, S.: Microarray synthesis through multiple-use PCR primer design. Bioinformatics 18, S128\u2013S135 (2002)","journal-title":"Bioinformatics"},{"key":"102_CR2","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1002\/gepi.20025","volume":"27","author":"A. Clark","year":"2004","unstructured":"Clark, A.: The role of haplotypes in candidate gene studies. Genet. Epid.\u00a027, 321\u2013333 (2004)","journal-title":"Genet. Epid."},{"key":"102_CR3","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1007\/BF02945456","volume":"18","author":"P. Bonizzoni","year":"2003","unstructured":"Bonizzoni, P., Vedova, G.D., Dondi, R., Li, J.: The haplotyping problem: An overview of computational models and solutions. Journal of Computer Science and Technology\u00a018, 675\u2013688 (2003)","journal-title":"Journal of Computer Science and Technology"},{"key":"102_CR4","doi-asserted-by":"crossref","unstructured":"Halldorsson, B., Bafna, V., Edwards, N., Lippert, R., Yooseph, S., Istrail, S.: A survey of computational methods for determining haplotypes. In: Proc. of the DIMACS\/RECOMB Satellite Workshop on Computational Methods for SNPs and Haplotype Inference, pp. 26\u201347 (2004)","DOI":"10.1007\/978-3-540-24719-7_3"},{"key":"102_CR5","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1002\/gepi.20024","volume":"27","author":"T. Niu","year":"2004","unstructured":"Niu, T.: Algorithms for inferring haplotypes. Genet. Epid.\u00a027, 334\u2013347 (2004)","journal-title":"Genet. Epid."},{"key":"102_CR6","doi-asserted-by":"crossref","unstructured":"Halperin, E., Hazan, E.: HAPLOFREQ - estimating haplotype frequencies efficiently. In: Proc. 9th Annual International Conference on Research in Computational Molecular Biology, pp. 553\u2013568 (2005)","DOI":"10.1007\/11415770_42"},{"key":"102_CR7","doi-asserted-by":"crossref","unstructured":"Gusfield, D.: Haplotyping by pure parsimony. In: Proc. 14th Annual Symp. on Combinatorial Pattern Matching, pp. 144\u2013155 (2003)","DOI":"10.1007\/3-540-44888-8_11"},{"key":"102_CR8","unstructured":"Lancia, G., Pinotti, C., Rizzi, R.: Haplotyping populations: complexity and approximations. Technical Report DIT-02-0080, University of Trento (2002)"},{"key":"102_CR9","doi-asserted-by":"publisher","first-page":"1773","DOI":"10.1093\/bioinformatics\/btg239","volume":"19","author":"L. Wang","year":"2003","unstructured":"Wang, L., Xu, Y.: Haplotype inference by maximum parsimony. Bioinformatics\u00a019, 1773\u20131780 (2003)","journal-title":"Bioinformatics"},{"key":"102_CR10","doi-asserted-by":"crossref","unstructured":"Brown, D., Harrower, I.: A New Integer Programming Formulation for the Pure Parsimony Problem in Haplotype Analysis. In: Proc. 4th International Workshop on Algorithms in Bioinformatics, pp. 254\u2013265 (2004)","DOI":"10.1007\/978-3-540-30219-3_22"},{"key":"102_CR11","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1287\/ijoc.1040.0085","volume":"16","author":"G. Lancia","year":"2004","unstructured":"Lancia, G., Pinotti, M., Rizzi, R.: Haplotyping populations by pure parsimony: Complexity of exact and approximation algorithms. INFORMS Journal on Computing\u00a016, 348\u2013359 (2004)","journal-title":"INFORMS Journal on Computing"},{"key":"102_CR12","doi-asserted-by":"crossref","unstructured":"Konwar, K., M\u0103ndoiu, I., Russell, A., Shvartsman, A.: Improved algorithms for multiplex PCR primer set selection with amplification length constraints. In: Proc. 3rd Asia-Pacific Bioinformatics Conference, pp. 41\u201350 (2005)","DOI":"10.1142\/9781860947322_0005"},{"key":"102_CR13","doi-asserted-by":"crossref","unstructured":"Hassin, R., Segev, D.: The set cover with pairs problem. In: Proc. 25th Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pp. 164\u2013176 (2005)","DOI":"10.1007\/11590156_13"},{"key":"102_CR14","doi-asserted-by":"publisher","first-page":"1261","DOI":"10.1089\/cmb.2005.12.1261","volume":"12","author":"Y.T. Huang","year":"2005","unstructured":"Huang, Y.T., Chao, K.M., Chen, T.: An approximation algorithm for haplotype inference by maximum parsimony. Journal of Computational Biology\u00a012, 1261\u20131274 (2005)","journal-title":"Journal of Computational Biology"},{"key":"102_CR15","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0020-0190(97)00182-8","volume":"64","author":"P. Slavik","year":"1997","unstructured":"Slavik, P.: Improved performance of the greedy algorithm for partial cover. Information Processing Letters\u00a064, 251\u2013254 (1997)","journal-title":"Information Processing Letters"},{"key":"102_CR16","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.jalgor.2004.04.002","volume":"53","author":"R. Gandhi","year":"2004","unstructured":"Gandhi, R., Khuller, S., Srinivasan, A.: Approximation algorithms for partial covering problems. Journal of Algorithms\u00a053, 55\u201384 (2004)","journal-title":"Journal of Algorithms"},{"issue":"3","key":"102_CR17","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/s004530010050","volume":"29","author":"U. Feige","year":"2001","unstructured":"Feige, U., Kortsarz, G., Peleg, D.: The dense k-subgraph problem. Algorithmica\u00a029(3), 410\u2013421 (2001)","journal-title":"Algorithmica"},{"key":"102_CR18","doi-asserted-by":"crossref","unstructured":"Khot, S.: Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique. In: Proc. 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 136\u2013145 (2004)","DOI":"10.1109\/FOCS.2004.59"},{"key":"102_CR19","doi-asserted-by":"crossref","unstructured":"Feige, U.: Relations between average case complexity and approximation complexity. In: Proc. 34th Annual ACM Symposium on Theory of Computing, pp. 534\u2013543 (2002)","DOI":"10.1145\/509907.509985"}],"container-title":["Lecture Notes in Computer Science","Computational Science \u2013 ICCS 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11758525_102","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,23]],"date-time":"2019-03-23T19:06:05Z","timestamp":1553367965000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11758525_102"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540343813","9783540343820"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/11758525_102","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}