{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T16:01:05Z","timestamp":1725897665874},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642322402"},{"type":"electronic","value":"9783642322419"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32241-9_17","type":"book-chapter","created":{"date-parts":[[2012,8,13]],"date-time":"2012-08-13T15:12:12Z","timestamp":1344870732000},"page":"193-203","source":"Crossref","is-referenced-by-count":2,"title":["Approximating the Rainbow \u2013 Better Lower and Upper Bounds"],"prefix":"10.1007","author":[{"given":"Alexandru","family":"Popa","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"17_CR1","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1002\/rsa.10102","volume":"23","author":"N. Alon","year":"2003","unstructured":"Alon, N., Jiang, T., Miller, Z., Pritikin, D.: Properly colored subgraphs and rainbow subgraphs in edge-colorings with local constraints. Random Structures & Algorithms\u00a023(4), 409\u2013433 (2003)","journal-title":"Random Structures & Algorithms"},{"issue":"1-3","key":"17_CR2","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/S0166-218X(01)00243-8","volume":"121","author":"Y. Asahiro","year":"2002","unstructured":"Asahiro, Y., Hassin, R., Iwama, K.: Complexity of finding dense subgraphs. Discrete Applied Mathematics\u00a0121(1-3), 15\u201326 (2002)","journal-title":"Discrete Applied Mathematics"},{"issue":"6","key":"17_CR3","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1287\/opre.29.6.1039","volume":"29","author":"R.G. Bland","year":"1981","unstructured":"Bland, R.G., Goldfarb, D., Todd, M.J.: The ellipsoid method: A survey. Operations Research\u00a029(6), 1039\u20131091 (1981)","journal-title":"Operations Research"},{"issue":"20","key":"17_CR4","doi-asserted-by":"publisher","first-page":"2666","DOI":"10.1016\/j.disc.2010.03.032","volume":"310","author":"S.M. Camacho","year":"2010","unstructured":"Camacho, S.M., Schiermeyer, I., Tuza, Z.: Approximation algorithms for the minimum rainbow subgraph problem. Discrete Mathematics\u00a0310(20), 2666\u20132670 (2010)","journal-title":"Discrete Mathematics"},{"issue":"5","key":"17_CR5","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1111\/j.1475-3995.2009.00716.x","volume":"16","author":"D. Catanzaro","year":"2009","unstructured":"Catanzaro, D., Labb, M.: The pure parsimony haplotyping problem: overview and computational advances. International Transactions in Operational Research\u00a016(5), 561\u2013584 (2009)","journal-title":"International Transactions in Operational Research"},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"Erd\u0151s, P., Tuza, Z.: Rainbow subgraphs in edge-colorings of complete graphs. In: Kennedy, J.W., Gimbel, J., Quintas, L.V. (eds.) Quo Vadis, Graph Theory? A Source Book for Challenges and Directions. Annals of Discrete Mathematics, vol.\u00a055, pp. 81\u201388. Elsevier (1993)","DOI":"10.1016\/S0167-5060(08)70377-7"},{"issue":"4","key":"17_CR7","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. Journal of the ACM\u00a045(4), 634\u2013652 (1998)","journal-title":"Journal of the ACM"},{"key":"17_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/3-540-44888-8_11","volume-title":"Combinatorial Pattern Matching","author":"D. Gusfield","year":"2003","unstructured":"Gusfield, D.: Haplotype Inference by Pure Parsimony. In: Baeza-Yates, R., Ch\u00e1vez, E., Crochemore, M. (eds.) CPM 2003. LNCS, vol.\u00a02676, pp. 144\u2013155. Springer, Heidelberg (2003)"},{"key":"17_CR9","unstructured":"Hahn, G., Thomassen, C.: Path and cycle sub-Ramsey numbers and an edge-colouring conjecture. Discrete Mathematics"},{"key":"17_CR10","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M.T., Jain, K., Lau, L.C., Mandoiu, I.I., Russell, A., Vazirani, V.V.: Minimum multicolored subgraph problem in multiplex pcr primer set selection and population haplotyping. In: International Conference on Computational Science, vol.\u00a0(2), pp. 758\u2013766 (2006)","DOI":"10.1007\/11758525_102"},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"Huang, Y.-T., Chao, K.-M., Chen, T.: An approximation algorithm for haplotype inference by maximum parsimony. In: SAC 2005, pp. 146\u2013150 (2005)","DOI":"10.1145\/1066677.1066714"},{"key":"17_CR12","unstructured":"Hubbell, E.: Unpublished manuscript (2002)"},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"3","key":"17_CR14","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/j.ipl.2010.11.005","volume":"111","author":"J. Katreni\u010d","year":"2011","unstructured":"Katreni\u010d, J., Schiermeyer, I.: Improved approximation bounds for the minimum rainbow subgraph problem. Inf. Process. Lett.\u00a0111(3), 110\u2013114 (2011)","journal-title":"Inf. Process. Lett."},{"issue":"0","key":"17_CR15","doi-asserted-by":"publisher","first-page":"765","DOI":"10.1016\/j.endm.2011.10.028","volume":"38","author":"M. Koch","year":"2011","unstructured":"Koch, M., Camacho, S.M., Schiermeyer, I.: Algorithmic approaches for the minimum rainbow subgraph problem. Electronic Notes in Discrete Mathematics\u00a038(0), 765\u2013770 (2011)","journal-title":"Electronic Notes in Discrete Mathematics"},{"issue":"4","key":"17_CR16","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.C., Rizzi, R.: Haplotyping populations by pure parsimony: Complexity of exact and approximation algorithms. INFORMS Journal on Computing\u00a016(4), 348\u2013359 (2004)","journal-title":"INFORMS Journal on Computing"},{"issue":"3","key":"17_CR17","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/j.orl.2005.05.007","volume":"34","author":"G. Lancia","year":"2006","unstructured":"Lancia, G., Rizzi, R.: A polynomial case of the parsimony haplotyping problem. Oper. Res. Lett.\u00a034(3), 289\u2013295 (2006)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"17_CR18","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1002\/rsa.3240030207","volume":"3","author":"V. R\u0151dl","year":"1992","unstructured":"R\u0151dl, V., Tuza, Z.: Rainbow subgraphs in properly edge-colored graphs. Random Structures & Algorithms\u00a03(2), 175\u2013182 (1992)","journal-title":"Random Structures & Algorithms"},{"issue":"1","key":"17_CR19","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/BF02579162","volume":"4","author":"M. Simonovits","year":"1984","unstructured":"Simonovits, M., S\u00f3s, V.T.: On restricted colourings of K\n                \n                  n\n                . Combinatorica\u00a04(1), 101\u2013110 (1984)","journal-title":"Combinatorica"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32241-9_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:58:48Z","timestamp":1620129528000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32241-9_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642322402","9783642322419"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32241-9_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}