{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,12]],"date-time":"2026-04-12T15:58:12Z","timestamp":1776009492528,"version":"3.50.1"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,8,15]],"date-time":"2014-08-15T00:00:00Z","timestamp":1408060800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,10]]},"DOI":"10.1007\/s00453-014-9926-0","type":"journal-article","created":{"date-parts":[[2014,8,14]],"date-time":"2014-08-14T19:12:21Z","timestamp":1408043541000},"page":"371-388","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Algorithmic and Hardness Results for the Colorful Components Problems"],"prefix":"10.1007","volume":"73","author":[{"given":"Anna","family":"Adamaszek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexandru","family":"Popa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,8,15]]},"reference":[{"key":"9926_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 ed. Springer, New York (1999)","DOI":"10.1007\/978-3-642-58412-1"},{"key":"9926_CR2","doi-asserted-by":"crossref","unstructured":"Avidor, A., Langberg, M.: The multi-multiway cut problem. Theoretical Computer Science 377(1\u20133), 35\u201342 (2007)","DOI":"10.1016\/j.tcs.2007.02.026"},{"issue":"3","key":"9926_CR3","doi-asserted-by":"crossref","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\u2014towards tight results. SIAM J. Comput. 27(3), 804\u2013915 (1998)","journal-title":"SIAM J. Comput."},{"key":"9926_CR4","doi-asserted-by":"crossref","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, volume 7933 of Lecture Notes in Computer Science, pp. 176\u2013187. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-38527-8_17"},{"key":"9926_CR5","doi-asserted-by":"crossref","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, volume 7354 of Lecture Notes in Computer Science, pp. 56\u201369. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-31265-6_5"},{"issue":"2","key":"9926_CR6","doi-asserted-by":"crossref","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. J. Comput. Syst. Sci. 57(2), 187\u2013199 (1998)","journal-title":"J. Comput. Syst. Sci."},{"key":"9926_CR7","doi-asserted-by":"crossref","unstructured":"He, G., Liu, J., Zhao, C.: Approximation algorithms for some graph partitioning problems. J. Graph Algorithms Appl. 4(2), 1\u201311 (2000)","DOI":"10.7155\/jgaa.00021"},{"key":"9926_CR8","volume-title":"Foundations of Comparative Genomics","author":"AR Mushegian","year":"2010","unstructured":"Mushegian, A.R.: Foundations of Comparative Genomics. Elsevier, Amsterdam (2010)"},{"issue":"3","key":"9926_CR9","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 15(3), 251\u2013277 (1981)","journal-title":"Theor. Comput. Sci."},{"key":"9926_CR10","doi-asserted-by":"crossref","unstructured":"Sankoff, D.: OMG! Orthologs for multiple genomes\u2014competing formulations\u2014(keynote talk). In: Chen, J., Wang, J., Zelikovsky, A. (eds.) ISBRA, volume 6674 of Lecture Notes in Computer Science, pp. 2\u20133. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-21260-4_2"},{"key":"9926_CR11","doi-asserted-by":"crossref","unstructured":"Savard, O.T., Swenson, K.M.: A graph-theoretic approach for inparalog detection. BMC Bioinform. 13(S-19), S16 (2012)","DOI":"10.1186\/1471-2105-13-S19-S16"},{"key":"9926_CR12","doi-asserted-by":"crossref","unstructured":"Zheng, C., Swenson, K.M., Lyons, E., Sankoff, D.: OMG! Orthologs in multiple genomes\u2014competing graph-theoretical formulations. In: Przytycka, T.M., Sagot, M.-F. (eds.) WABI, volume 6833 of Lecture Notes in Computer Science, pp. 364\u2013375. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-23038-7_30"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9926-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9926-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9926-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,13]],"date-time":"2019-08-13T22:58:18Z","timestamp":1565737098000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9926-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,15]]},"references-count":12,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,10]]}},"alternative-id":["9926"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9926-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,8,15]]}}}