{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:26:18Z","timestamp":1759638378502,"version":"3.40.3"},"publisher-location":"Cham","reference-count":11,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319193144"},{"type":"electronic","value":"9783319193151"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-19315-1_2","type":"book-chapter","created":{"date-parts":[[2015,6,6]],"date-time":"2015-06-06T10:42:08Z","timestamp":1433587328000},"page":"13-23","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Approximation and Hardness Results for the Maximum Edges in Transitive Closure Problem"],"prefix":"10.1007","author":[{"given":"Anna","family":"Adamaszek","sequence":"first","affiliation":[]},{"given":"Guillaume","family":"Blin","sequence":"additional","affiliation":[]},{"given":"Alexandru","family":"Popa","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,7]]},"reference":[{"key":"2_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1007\/978-3-642-54423-1_59","volume-title":"LATIN 2014: Theoretical Informatics","author":"A Adamaszek","year":"2014","unstructured":"Adamaszek, A., Popa, A.: Algorithmic and hardness results for the colorful components problems. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol. 8392, pp. 683\u2013694. Springer, Heidelberg (2014)"},{"issue":"1\u20133","key":"2_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. Theoret. Comput. Sci. 377(1\u20133), 35\u201342 (2007)","journal-title":"Theoret. Comput. Sci."},{"key":"2_CR3","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: Demetrescu, C., Marchetti-Spaccamela, A., Bonifaci, V. (eds.) SEA 2013. LNCS, vol. 7933, pp. 176\u2013187. Springer, Heidelberg (2013)"},{"key":"2_CR4","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. 7354, pp. 56\u201369. Springer, Heidelberg (2012)"},{"issue":"2","key":"2_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.7155\/jgaa.00021","volume":"4","author":"G He","year":"2000","unstructured":"He, G., Liu, J., Zhao, C.: Approximation algorithms for some graph partitioning problems. J. Graph Algorithms Appl. 4(2), 1\u201311 (2000)","journal-title":"J. Graph Algorithms Appl."},{"issue":"2","key":"2_CR6","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01202286","volume":"4","author":"E Petrank","year":"1994","unstructured":"Petrank, E.: The hardness of approximation: gap location. Comput. Complex. 4(2), 133\u2013157 (1994)","journal-title":"Comput. Complex."},{"key":"2_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/978-3-642-30642-6_26","volume-title":"Computer Science \u2013 Theory and Applications","author":"R Rizzi","year":"2012","unstructured":"Rizzi, R., Sikora, F.: Some results on more flexible versions of graph motif. In: Hirsch, E.A., Karhum\u00e4ki, J., Lepist\u00f6, A., Prilutskii, M. (eds.) CSR 2012. LNCS, vol. 7353, pp. 278\u2013289. Springer, Heidelberg (2012)"},{"key":"2_CR8","series-title":"Lecture Notes in Computer Science","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. In: Chen, J., Wang, J., Zelikovsky, A. (eds.) ISBRA 2011. LNCS, vol. 6674, pp. 2\u20133. Springer, Heidelberg (2011)"},{"issue":"S\u201319","key":"2_CR9","doi-asserted-by":"publisher","first-page":"S16","DOI":"10.1186\/1471-2105-13-S19-S16","volume":"13","author":"OT Savard","year":"2012","unstructured":"Savard, O.T., Swenson, K.M.: A graph-theoretic approach for inparalog detection. BMC Bioinform. 13(S\u201319), S16 (2012)","journal-title":"BMC Bioinform."},{"key":"2_CR10","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 \u2013 competing graph-theoretical formulations. In: Przytycka, T.M., Sagot, M.-F. (eds.) WABI 2011. LNCS, vol. 6833, pp. 364\u2013375. Springer, Heidelberg (2011)"},{"issue":"1","key":"2_CR11","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(1), 103\u2013128 (2007)","journal-title":"Theory Comput."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-19315-1_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T04:05:53Z","timestamp":1675137953000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-19315-1_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319193144","9783319193151"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-19315-1_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"7 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}