{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:32:18Z","timestamp":1725564738074},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540204527"},{"type":"electronic","value":"9783540398905"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-39890-5_16","type":"book-chapter","created":{"date-parts":[[2010,9,4]],"date-time":"2010-09-04T01:16:57Z","timestamp":1283563017000},"page":"180-191","source":"Crossref","is-referenced-by-count":15,"title":["An FPT Algorithm for Set Splitting"],"prefix":"10.1007","author":[{"given":"Frank","family":"Dehne","sequence":"first","affiliation":[]},{"given":"Michael R.","family":"Fellows","sequence":"additional","affiliation":[]},{"given":"Frances A.","family":"Rosamond","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"16_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/3-540-45253-2_4","volume-title":"Algorithms - ESA 2000","author":"A.A. Ageev","year":"2000","unstructured":"Ageev, A.A., Sviridenko, M.I.: An approximation algorithm for hypergraph max k-cut with given sizes of parts. In: Paterson, M. (ed.) ESA 2000. LNCS, vol.\u00a01879, pp. 32\u201341. Springer, Heidelberg (2000)"},{"key":"16_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/3-540-44985-X_10","volume-title":"Algorithm Theory - SWAT 2000","author":"J. Alber","year":"2000","unstructured":"Alber, J., Bodlaender, H.L., Fernau, H., Niedermeier, R.: Fixed parameter algorithms for planar dominating set and related problems. In: Halld\u00f3rsson, M.M. (ed.) SWAT 2000. LNCS, vol.\u00a01851, pp. 97\u2013110. Springer, Heidelberg (2000)"},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"Andersson, G., Engebretsen, L.: Better approximation algorithms and tighter analysis for set splitting and not-all-equal sat. In: ECCCTR: Electronic Colloquium on Computational Complexity (1997)","DOI":"10.1016\/S0020-0190(98)00021-0"},{"key":"16_CR4","doi-asserted-by":"crossref","unstructured":"Arora, S., Karger, D., Karpinski, M.: Polynomial time approximation schemes for dense instances of NP-hard problems. In: Proc. ACM STOC, pp. 284\u2013293 (1995)","DOI":"10.1145\/225058.225140"},{"key":"16_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/3-540-48224-5_23","volume-title":"Automata, Languages and Programming","author":"L. Cai","year":"2001","unstructured":"Cai, L., Juedes, D.: Subexponential parameterized algorithms collapse the whierarchy. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, p. 273. Springer, Heidelberg (2001)"},{"key":"16_CR6","doi-asserted-by":"crossref","unstructured":"Cheetham, J., Dehne, F., Rau-Chaplin, A., Stege, U., Taillon, P.J.: Solving large FPT problems on coarse grained parallel machines. Journal of Computer and System Sciences (to appear)","DOI":"10.1016\/S0022-0000(03)00075-8"},{"key":"16_CR7","volume-title":"Proc. Computing: The Australasian Theory Symposium (CATS 2003 )","author":"R.D. Downey","year":"2003","unstructured":"Downey, R.D., Estivill-Castro, V., Fellows, M.R., Prieto-Rodriguez, E., Rosamond, F.A.: Cutting up is hard to do: The parameterized complexity of k-cut and related problems. In: Proc. Computing: The Australasian Theory Symposium (CATS 2003 ), Elsevier Electronic Notes in Computer Science, Adelaide (2003) (to appear)"},{"key":"16_CR8","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1998","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1998)"},{"key":"16_CR9","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)"},{"key":"16_CR10","doi-asserted-by":"crossref","unstructured":"Hastad, J.: Some optimal inapproximability results. In: Proc. ACM STOC, pp. 1\u201310 (1997)","DOI":"10.1145\/258533.258536"},{"key":"16_CR11","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J.E. Hopkroft","year":"1973","unstructured":"Hopkroft, J.E., Karp, R.M.: An n5\/2 algorithm for maximum matching in bipartite graphs. SIAM J. Comput.\u00a02, 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"16_CR12","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/0020-0190(96)00046-4","volume":"58","author":"V. Kann","year":"1996","unstructured":"Kann, V., Lagergren, J., Panconesi, A.: Approximability of maximum splitting of k-sets and some other apx-complete problems. Information Processing Letters\u00a058(3), 105\u2013110 (1996)","journal-title":"Information Processing Letters"},{"key":"16_CR13","unstructured":"Lovasz, L.: Coverings and colorings of hypergraphs. In: Proc. 4th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, pp. 3\u201312 (1973)"},{"key":"16_CR14","volume-title":"Data Structures And Algorithms","author":"K. Mehlhorn","year":"1990","unstructured":"Mehlhorn, K.: Data Structures And Algorithms. Springer, Heidelberg (1990)"},{"key":"16_CR15","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. Computational Complexity\u00a04, 133\u2013157 (1994)","journal-title":"Computational Complexity"},{"key":"16_CR16","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1007\/3-540-45357-1_62","volume-title":"Advances in Knowledge Discovery and Data Mining","author":"H. Zhang","year":"2001","unstructured":"Zhang, H., Ling, C.X.: An improved learning algorithm for augmented naive Bayes. In: Cheung, D., Williams, G.J., Li, Q. (eds.) PAKDD 2001. LNCS (LNAI), vol.\u00a02035, pp. 581\u2013586. Springer, Heidelberg (2001)"},{"key":"16_CR17","unstructured":"Zwick, U.: Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint. In: Proc. SODA, pp. 201\u2013220 (1998)"},{"key":"16_CR18","doi-asserted-by":"crossref","unstructured":"Zwick, U.: Outward rotations: A tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems. In: Proc. ACM STOC, pp. 679\u2013687 (1999)","DOI":"10.1145\/301250.301431"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-39890-5_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,8]],"date-time":"2021-11-08T06:08:58Z","timestamp":1636351738000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-39890-5_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540204527","9783540398905"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-39890-5_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}