{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T10:21:51Z","timestamp":1725790911953},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642544224"},{"type":"electronic","value":"9783642544231"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-642-54423-1_59","type":"book-chapter","created":{"date-parts":[[2014,3,24]],"date-time":"2014-03-24T23:02:27Z","timestamp":1395702147000},"page":"683-694","source":"Crossref","is-referenced-by-count":1,"title":["Algorithmic and Hardness Results for the Colorful Components Problems"],"prefix":"10.1007","author":[{"given":"Anna","family":"Adamaszek","sequence":"first","affiliation":[]},{"given":"Alexandru","family":"Popa","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"59_CR1","doi-asserted-by":"crossref","unstructured":"Ausiello, G., Protasi, M., Marchetti-Spaccamela, A., Gambosi, G., Crescenzi, P., Kann, V.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, 1st edn. Springer-Verlag New York, Inc., Secaucus (1999)","DOI":"10.1007\/978-3-642-58412-1_1"},{"issue":"1-3","key":"59_CR2","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/j.tcs.2007.02.026","volume":"377","author":"A. Avidor","year":"2007","unstructured":"Avidor, A., Langberg, M.: The multi-multiway cut problem. Theoretical Computer Science\u00a0377(1-3), 35\u201342 (2007)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"59_CR3","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1137\/S0097539796302531","volume":"27","author":"M. Bellare","year":"1998","unstructured":"Bellare, M., Goldreich, O., Sudan, M.: Free bits, PCPs, and nonapproximability - towards tight results. SIAM Journal on Computing\u00a027(3), 804\u2013915 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"59_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/978-3-642-38527-8_17","volume-title":"Experimental Algorithms","author":"S. Bruckner","year":"2013","unstructured":"Bruckner, S., H\u00fcffner, F., Komusiewicz, C., Niedermeier, R.: Evaluation of ILP-based approaches for partitioning into colorful components. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol.\u00a07933, pp. 176\u2013187. Springer, Heidelberg (2013)"},{"key":"59_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1007\/978-3-642-31265-6_5","volume-title":"Combinatorial Pattern Matching","author":"S. Bruckner","year":"2012","unstructured":"Bruckner, S., H\u00fcffner, F., Komusiewicz, C., Niedermeier, R., Thiel, S., Uhlmann, J.: Partitioning into colorful components by minimum edge deletions. In: K\u00e4rkk\u00e4inen, J., Stoye, J. (eds.) CPM 2012. LNCS, vol.\u00a07354, pp. 56\u201369. Springer, Heidelberg (2012)"},{"issue":"2","key":"59_CR6","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1006\/jcss.1998.1587","volume":"57","author":"U. Feige","year":"1998","unstructured":"Feige, U., Kilian, J.: Zero knowledge and the chromatic number. Journal of Computer and System Sciences\u00a057(2), 187\u2013199 (1998)","journal-title":"Journal of Computer and System Sciences"},{"key":"59_CR7","doi-asserted-by":"crossref","unstructured":"He, G., Liu, J., Zhao, C.: Approximation algorithms for some graph partitioning problems. Journal of Graph Algorithms and Applications\u00a04(2) (2000)","DOI":"10.7155\/jgaa.00021"},{"key":"59_CR8","unstructured":"Mushegian, A.R.: Foundations of Comparative Genomics. Elsevier Science (2010)"},{"issue":"3","key":"59_CR9","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0304-3975(81)90081-5","volume":"15","author":"A. Paz","year":"1981","unstructured":"Paz, A., Moran, S.: Non deterministic polynomial optimization problems and their approximations. Theoretical Computer Science\u00a015(3), 251\u2013277 (1981)","journal-title":"Theoretical Computer Science"},{"key":"59_CR10","series-title":"LNBI","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/978-3-642-21260-4_2","volume-title":"Bioinformatics Research and Applications","author":"D. Sankoff","year":"2011","unstructured":"Sankoff, D.: OMG! Orthologs for multiple genomes - competing formulations - (keynote talk). In: Chen, J., Wang, J., Zelikovsky, A. (eds.) ISBRA 2011. LNCS (LNBI), vol.\u00a06674, pp. 2\u20133. Springer, Heidelberg (2011)"},{"key":"59_CR11","doi-asserted-by":"crossref","unstructured":"Savard, O.T., Swenson, K.M.: A graph-theoretic approach for inparalog detection. BMC Bioinformatics\u00a013(S-19), S16 (2012)","DOI":"10.1186\/1471-2105-13-S19-S16"},{"key":"59_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1007\/978-3-642-23038-7_30","volume-title":"Algorithms in Bioinformatics","author":"C. Zheng","year":"2011","unstructured":"Zheng, C., Swenson, K., Lyons, E., Sankoff, D.: OMG! Orthologs in multiple genomes - competing graph-theoretical formulations. In: Przytycka, T.M., Sagot, M.-F. (eds.) WABI 2011. LNCS, vol.\u00a06833, pp. 364\u2013375. Springer, Heidelberg (2011)"}],"container-title":["Lecture Notes in Computer Science","LATIN 2014: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-54423-1_59","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T08:53:50Z","timestamp":1558860830000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-54423-1_59"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783642544224","9783642544231"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-54423-1_59","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}