{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:58:06Z","timestamp":1725537486718},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642041273"},{"type":"electronic","value":"9783642041280"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-04128-0_58","type":"book-chapter","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T14:16:36Z","timestamp":1252937796000},"page":"647-658","source":"Crossref","is-referenced-by-count":4,"title":["Constant Ratio Fixed-Parameter Approximation of the Edge Multicut Problem"],"prefix":"10.1007","author":[{"given":"D\u00e1niel","family":"Marx","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Igor","family":"Razgon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1-3","key":"58_CR1","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1023\/B:MACH.0000033116.57574.95","volume":"56","author":"N. Bansal","year":"2004","unstructured":"Bansal, N., Blum, A., Chawla, S.: Correlation clustering. Machine Learning\u00a056(1-3), 89\u2013113 (2004)","journal-title":"Machine Learning"},{"key":"58_CR2","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/978-3-540-85238-4_11","volume-title":"MFCS 2008: Proceedings of the 33rd international symposium on Mathematical Foundations of Computer Science","author":"H.L. Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Fellows, M.R., Heggernes, P., Mancini, F., Papadopoulos, C., Rosamond, F.: Clustering with partial information. In: MFCS 2008: Proceedings of the 33rd international symposium on Mathematical Foundations of Computer Science, pp. 144\u2013155. Springer, Heidelberg (2008)"},{"key":"58_CR3","unstructured":"Bousquet, N., Daligault, J., Thomasse, S., Yeo, A.: A polynomial kernel for multicut in trees. In: Albers, S., Marion, J.-Y. (eds.) 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009). Leibniz International Proceedings in Informatics, vol.\u00a03, pp. 183\u2013194. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany (2009)"},{"key":"58_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/11847250_9","volume-title":"Parameterized and Exact Computation","author":"L. Cai","year":"2006","unstructured":"Cai, L., Huang, X.: Fixed-parameter approximation: conceptual framework and approximability results. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 96\u2013108. Springer, Heidelberg (2006)"},{"issue":"2","key":"58_CR5","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/s00037-006-0210-9","volume":"15","author":"S. Chawla","year":"2006","unstructured":"Chawla, S., Krauthgamer, R., Kumar, R., Rabani, Y., Sivakumar, D.: On the hardness of approximating multicut and sparsest-cut. Comput. Complexity\u00a015(2), 94\u2013114 (2006)","journal-title":"Comput. Complexity"},{"key":"58_CR6","doi-asserted-by":"crossref","unstructured":"Chen, J., Liu, Y., Lu, S., O\u2019Sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM\u00a055(5) (2008)","DOI":"10.1145\/1411509.1411511"},{"key":"58_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/11847250_10","volume-title":"Parameterized and Exact Computation","author":"Y. Chen","year":"2006","unstructured":"Chen, Y., Grohe, M., Gr\u00fcber, M.: On parameterized approximability. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 109\u2013120. Springer, Heidelberg (2006)"},{"issue":"2-3","key":"58_CR8","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1016\/j.tcs.2006.05.008","volume":"361","author":"E.D. Demaine","year":"2006","unstructured":"Demaine, E.D., Emanuel, D., Fiat, A., Immorlica, N.: Correlation clustering in general weighted graphs. Theor. Comput. Sci.\u00a0361(2-3), 172\u2013187 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"58_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/11847250_11","volume-title":"Parameterized and Exact Computation","author":"R. Downey","year":"2006","unstructured":"Downey, R., Fellows, M., McCartin, C.: Parameterized approximation algorithms. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 121\u2013129. Springer, Heidelberg (2006)"},{"key":"58_CR10","series-title":"Monographs in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)"},{"issue":"1","key":"58_CR11","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"M.R. Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F.A., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci.\u00a0410(1), 53\u201361 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"58_CR12","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"issue":"2","key":"58_CR13","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1137\/S0097539793243016","volume":"25","author":"N. Garg","year":"1996","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Approximate max-flow min-(multi)cut theorems and their applications. SIAM J. Comput.\u00a025(2), 235\u2013251 (1996)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"58_CR14","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1016\/j.ejor.2007.02.014","volume":"186","author":"J. Guo","year":"2008","unstructured":"Guo, J., H\u00fcffner, F., Kenar, E., Niedermeier, R., Uhlmann, J.: Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs. European J. Oper. Res.\u00a0186(2), 542\u2013553 (2008)","journal-title":"European J. Oper. Res."},{"issue":"3","key":"58_CR15","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1002\/net.20081","volume":"46","author":"J. Guo","year":"2005","unstructured":"Guo, J., Niedermeier, R.: Fixed-parameter tractability and data reduction for multicut in trees. Networks\u00a046(3), 124\u2013135 (2005)","journal-title":"Networks"},{"issue":"1","key":"58_CR16","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1093\/comjnl\/bxm040","volume":"51","author":"F. H\u00fcffner","year":"2008","unstructured":"H\u00fcffner, F., Niedermeier, R., Wernicke, S.: Techniques for practical fixed-parameter algorithms. The Computer Journal\u00a051(1), 7\u201325 (2008)","journal-title":"The Computer Journal"},{"key":"58_CR17","first-page":"767","volume-title":"Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing","author":"S. Khot","year":"2002","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, pp. 767\u2013775. ACM, New York (2002) (electronic)"},{"key":"58_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/11847250_8","volume-title":"Parameterized and Exact Computation","author":"Y. Liu","year":"2006","unstructured":"Liu, Y., Lu, S., Chen, J., Sze, S.-H.: Greedy localization and color-coding: improved matching and packing algorithms. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 84\u201395. Springer, Heidelberg (2006)"},{"issue":"3","key":"58_CR19","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.tcs.2005.10.007","volume":"351","author":"D. Marx","year":"2006","unstructured":"Marx, D.: Parameterized graph separation problems. Theoretical Computer Science\u00a0351(3), 394\u2013406 (2006)","journal-title":"Theoretical Computer Science"},{"key":"58_CR20","doi-asserted-by":"crossref","unstructured":"Marx, D.: Chordal deletion is fixed-parameter tractable. To appear in Algorithmica (2008)","DOI":"10.1007\/s00453-008-9233-8"},{"issue":"1","key":"58_CR21","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1093\/comjnl\/bxm048","volume":"51","author":"D. Marx","year":"2008","unstructured":"Marx, D.: Parameterized complexity and approximation algorithms. The Computer Journal\u00a051(1), 60\u201378 (2008)","journal-title":"The Computer Journal"},{"key":"58_CR22","doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications, vol.\u00a031 (2006)","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"58_CR23","doi-asserted-by":"crossref","unstructured":"Razgon, I., O\u2019Sullivan, B.: Almost 2-sat is fixed-parameter tractable. CoRR, abs\/0801.1300 (2008)","DOI":"10.1007\/978-3-540-70575-8_45"},{"key":"58_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/978-3-540-70575-8_45","volume-title":"Automata, Languages and Programming","author":"I. Razgon","year":"2008","unstructured":"Razgon, I., O\u2019Sullivan, B.: Almost 2-sat is fixed-parameter tractable (extended abstract). In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 551\u2013562. Springer, Heidelberg (2008)"},{"issue":"4","key":"58_CR25","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"B. Reed","year":"2004","unstructured":"Reed, B., Smith, K., Vetta, A.: Finding odd cycle transversals. Operations Research Letters\u00a032(4), 299\u2013301 (2004)","journal-title":"Operations Research Letters"},{"key":"58_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1007\/978-3-540-79709-8_32","volume-title":"Computer Science \u2013 Theory and Applications","author":"M. Xiao","year":"2008","unstructured":"Xiao, M.: Algorithms for multiterminal cuts. In: Hirsch, E.A., Razborov, A.A., Semenov, A., Slissenko, A. (eds.) Computer Science \u2013 Theory and Applications. LNCS, vol.\u00a05010, pp. 314\u2013325. Springer, Heidelberg (2008)"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04128-0_58","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T11:22:39Z","timestamp":1558524159000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04128-0_58"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642041273","9783642041280"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04128-0_58","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}