{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:12:46Z","timestamp":1759637566633},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540230717"},{"type":"electronic","value":"9783540286394"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-28639-4_24","type":"book-chapter","created":{"date-parts":[[2010,9,20]],"date-time":"2010-09-20T20:25:35Z","timestamp":1285014335000},"page":"271-280","source":"Crossref","is-referenced-by-count":22,"title":["Greedy Localization, Iterative Compression, and Modeled Crown Reductions: New FPT Techniques, an Improved Algorithm for Set Splitting, and a Novel 2k Kernelization for Vertex Cover"],"prefix":"10.1007","author":[{"given":"Frank","family":"Dehne","sequence":"first","affiliation":[]},{"given":"Mike","family":"Fellows","sequence":"additional","affiliation":[]},{"given":"Frances","family":"Rosamond","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Shaw","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"24_CR1","unstructured":"Abu-Khzam, F.N., Collins, R.L., Fellows, M.R., Langston, M.A., Suters, W.H., Symons, C.T.: Kernelization algorithms for the Vertex Cover problem: theory and experiments. In: Proceedings ALENEX 2004, ACM\/SIAM (2004)"},{"key":"24_CR2","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":"24_CR3","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N. Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-Coding. Journal of the ACM\u00a042, 844\u2013856 (1995)","journal-title":"Journal of the ACM"},{"key":"24_CR4","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. Information Processing Letters\u00a065, 305\u2013311 (1998)","journal-title":"Information Processing Letters"},{"key":"24_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/978-3-540-30559-0_22","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"B. Chor","year":"2004","unstructured":"Chor, B., Fellows, M., Juedes, D.: Linear Kernels in Linear Time, or How to Save k Colors in O(n2) Steps). In: Hromkovi\u010d, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol.\u00a03353, pp. 257\u2013269. Springer, Heidelberg (2004)"},{"key":"24_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/3-540-45294-X_11","volume-title":"FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science","author":"J. Chen","year":"2001","unstructured":"Chen, J., Friesen, D.K., Jia, W., Kanj, I.A.: Using Nondeterminism to Design Efficient Deterministic Algorithms. In: Hariharan, R., Mukund, M., Vinay, V. (eds.) FSTTCS 2001. LNCS, vol.\u00a02245, pp. 120\u2013131. Springer, Heidelberg (2001)"},{"key":"24_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/978-3-540-39890-5_16","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"F. Dehne","year":"2003","unstructured":"Dehne, F., Fellows, M., Rosamond, F.: An FPT Algorithm for Set Splitting. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol.\u00a02880, pp. 180\u2013191. Springer, Heidelberg (2003)"},{"key":"24_CR8","doi-asserted-by":"crossref","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. Springer, Heidelberg (1999)"},{"key":"24_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-39890-5_1","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M. Fellows","year":"2003","unstructured":"Fellows, M.: 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_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/978-3-540-30140-0_29","volume-title":"Algorithms \u2013 ESA 2004","author":"M. Fellows","year":"2004","unstructured":"Fellows, M., Knauer, C., Nishimura, N., Ragde, P., Rosamond, F., Stege, U., Thilikos, D., Whitesides, S.: Faster Fixed-Parameter Tractable Algorithms for Matching and Packing Problems. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol.\u00a03221, pp. 311\u2013322. Springer, Heidelberg (2004) (to appear)"},{"key":"24_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-540-30559-0_20","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M. Fellows","year":"2004","unstructured":"Fellows, M., Heggernes, P., Rosamond, F., Sloper, C., Telle, J.A.: Exact Algorithms for Finding k Disjoint Triangles in an Arbitrary Graph. In: Hromkovi\u010d, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol.\u00a03353, pp. 235\u2013244. Springer, Heidelberg (2004)"},{"key":"24_CR12","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)"},{"key":"24_CR13","unstructured":"Jia, W., Zhang, C., Chen, J.: An Efficient Parameterized Algorithm for Set Packing. To appear in Journal of Algorithms (2003) (manuscript)"},{"key":"24_CR14","unstructured":"Marx, D.: Chordal Deletion is Fixed-Parameter Tractable (2004) (manuscript)"},{"key":"24_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/978-3-540-28639-4_12","volume-title":"Parameterized and Exact Computation","author":"L. Mathieson","year":"2004","unstructured":"Mathieson, L., Prieto, E., Shaw, P.: Packing Edge Disjoint Triangles: A Parameterized View. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol.\u00a03162, pp. 127\u2013137. Springer, Heidelberg (2004)"},{"key":"24_CR16","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms, Habilitationschrift, University of Tubingen (2002)"},{"key":"24_CR17","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":"24_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1007\/978-3-540-45078-8_41","volume-title":"Algorithms and Data Structures","author":"E. Prieto","year":"2003","unstructured":"Prieto, E., Sloper, C.: Either\/Or: Using Vertex Cover Structure in Designing FPT Algorithms\u2013the Case of k-Internal Spanning Tree. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol.\u00a02748, pp. 474\u2013483. Springer, Heidelberg (2003)"},{"key":"24_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1007\/978-3-540-28639-4_13","volume-title":"Parameterized and Exact Computation","author":"E. Prieto","year":"2004","unstructured":"Prieto, E., Sloper, C.: Looking at the Stars. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol.\u00a03162, pp. 138\u2013148. Springer, Heidelberg (2004)"},{"key":"24_CR20","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, 299\u2013301 (2004)","journal-title":"Operations Research Letters"},{"key":"24_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1007\/3-540-36478-1_17","volume-title":"Combinatorial Optimization - Eureka, You Shrink!","author":"G.J. Woeginger","year":"2003","unstructured":"Woeginger, G.J.: Exact Algorithms for NP-Hard Problems: A Survey. In: J\u00fcnger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization - Eureka, You Shrink! LNCS, vol.\u00a02570, pp. 184\u2013207. Springer, Heidelberg (2003)"},{"key":"24_CR22","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)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-28639-4_24.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T03:29:58Z","timestamp":1620012598000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-28639-4_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540230717","9783540286394"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-28639-4_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}