{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T01:21:37Z","timestamp":1761960097189,"version":"build-2065373602"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642112683"},{"type":"electronic","value":"9783642112690"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","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-11269-0_24","type":"book-chapter","created":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T08:36:15Z","timestamp":1259656575000},"page":"288-299","source":"Crossref","is-referenced-by-count":8,"title":["Even Faster Algorithm for Set Splitting!"],"prefix":"10.1007","author":[{"given":"Daniel","family":"Lokshtanov","sequence":"first","affiliation":[]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"6","key":"24_CR1","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/S0020-0190(98)00021-0","volume":"65","author":"G. Andersson","year":"1998","unstructured":"Andersson, G., Engebretsen, L.: Better approximation algorithms for SET SPLITTING and NOT-ALL-EQUAL SAT. Inf. Process. Lett.\u00a065(6), 305\u2013311 (1998)","journal-title":"Inf. Process. Lett."},{"key":"24_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1007\/978-3-540-73545-8_52","volume-title":"Computing and Combinatorics","author":"J. Chen","year":"2007","unstructured":"Chen, J., Lu, S.: Improved algorithms for weighted and unweighted set splitting problems. In: Lin, G. (ed.) COCOON 2007. LNCS, vol.\u00a04598, pp. 537\u2013547. Springer, Heidelberg (2007)"},{"issue":"3","key":"24_CR3","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1016\/j.dam.2007.03.026","volume":"156","author":"M. Chleb\u00edk","year":"2008","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Crown reductions for the minimum weighted vertex cover problem. Discrete Applied Mathematics\u00a0156(3), 292\u2013312 (2008)","journal-title":"Discrete Applied Mathematics"},{"key":"24_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1007\/978-3-540-39890-5_16","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"F.K.H.A. Dehne","year":"2003","unstructured":"Dehne, F.K.H.A., Fellows, M.R., Rosamond, F.A.: An FPT algorithm for set splitting. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol.\u00a02880, pp. 180\u2013191. Springer, Heidelberg (2003)"},{"key":"24_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/978-3-540-28639-4_24","volume-title":"Parameterized and Exact Computation","author":"F.K.H.A. Dehne","year":"2004","unstructured":"Dehne, F.K.H.A., Fellows, M.R., Rosamond, F.A., Shaw, P.: Greedy localization, iterative compression, modeled crown reductions: New fpt techniques, an improved algorithm for set splitting, and a novel 2k kernelization for vertex cover. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol.\u00a03162, pp. 271\u2013280. Springer, Heidelberg (2004)"},{"key":"24_CR6","first-page":"5","volume":"11","author":"P. Erd\u0151s","year":"1963","unstructured":"Erd\u0151s, P.: On a combinatorial problem, I. Nordisk Mat. Tidskrift\u00a011, 5\u201310 (1963)","journal-title":"Nordisk Mat. Tidskrift"},{"key":"24_CR7","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/BF01897152","volume":"15","author":"P. Erd\u0151s","year":"1964","unstructured":"Erd\u0151s, P.: On a combinatorial problem, II. Acta Math, Hungary\u00a015, 445\u2013447 (1964)","journal-title":"Acta Math, Hungary"},{"key":"24_CR8","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M.R. Fellows","year":"2003","unstructured":"Fellows, M.R.: Blow-ups, win\/win\u2019s, and crown rules: Some new directions in FPT. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol.\u00a02880, pp. 1\u201312. Springer, Heidelberg (2003)"},{"key":"24_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/11523468_16","volume-title":"Automata, Languages and Programming","author":"F.V. Fomin","year":"2005","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and conquer: Domination - a case study. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 191\u2013203. Springer, Heidelberg (2005)"},{"key":"24_CR10","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and conquer: a simple o(2$^{\\mbox{0.288{\\it }}}$) independent set algorithm. In: SODA, pp. 18\u201325 (2006)","DOI":"10.1145\/1109557.1109560"},{"issue":"2","key":"24_CR11","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1016\/S0166-218X(02)00463-8","volume":"131","author":"A. Frank","year":"2003","unstructured":"Frank, A., Kir\u00e1ly, T., Kriesell, M.: On decomposing a hypergraph into k connected sub-hypergraphs. Discrete Applied Mathematics\u00a0131(2), 373\u2013383 (2003)","journal-title":"Discrete Applied Mathematics"},{"issue":"6","key":"24_CR12","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM\u00a042(6), 1115\u20131145 (1995)","journal-title":"J. ACM"},{"key":"24_CR13","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"24_CR14","unstructured":"Lokshtanov, D., Sloper, C.: Fixed parameter set splitting, linear kernel and improved running time. In: ACiD. Texts in Algorithmics, vol.\u00a04, pp. 105\u2013113 (2005)"},{"key":"24_CR15","unstructured":"Lov\u00e1sz, L.: Covering and coloring of hypergraphs. In: Proceedings of the 4th Southeastern Conference on Combinatorics, Graph Theory and Computing. Utilitas Mathematica Publishing, pp. 3\u201312 (1973)"},{"key":"24_CR16","unstructured":"Prieto, E.: The method of extremal structure on the k-maximum cut problem. In: CATS, pp. 119\u2013126 (2005)"},{"issue":"1","key":"24_CR17","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1002\/(SICI)1098-2418(200001)16:1<4::AID-RSA2>3.0.CO;2-2","volume":"16","author":"J. Radhakrishnan","year":"2000","unstructured":"Radhakrishnan, J., Srinivasan, A.: Improved bounds and algorithms for hypergraph 2-coloring. Random Struct. Algorithms\u00a016(1), 4\u201332 (2000)","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"24_CR18","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.ipl.2007.05.014","volume":"104","author":"V. Raman","year":"2007","unstructured":"Raman, V., Saurabh, S.: Improved fixed parameter tractable algorithms for two \u201cedge\u201d problems: MAXCUT and MAXDAG. Inf. Process. Lett.\u00a0104(2), 65\u201372 (2007)","journal-title":"Inf. Process. Lett."},{"key":"24_CR19","unstructured":"Sloper, C.: Techniques in parameterized algorithm design. PhD thesis, University of Bergen (2005)"},{"key":"24_CR20","unstructured":"Wahlstr\u00f6m, M.: Algorithms, measures, and upper bounds for satisfiability and related problems. PhD thesis, Linkp\u0308ing University (2007)"},{"issue":"1-3","key":"24_CR21","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/j.dam.2002.07.001","volume":"142","author":"J. Zhang","year":"2004","unstructured":"Zhang, J., Ye, Y., Han, Q.: Improved approximations for max set splitting and max NAE SAT. Discrete Applied Mathematics\u00a0142(1-3), 133\u2013149 (2004)","journal-title":"Discrete Applied Mathematics"},{"key":"24_CR22","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: STOC, pp. 679\u2013687 (1999)","DOI":"10.1145\/301250.301431"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11269-0_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,18]],"date-time":"2023-02-18T00:34:58Z","timestamp":1676680498000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-11269-0_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642112683","9783642112690"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11269-0_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}