{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:15:46Z","timestamp":1759637746903},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540281016"},{"type":"electronic","value":"9783540317111"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11534273_5","type":"book-chapter","created":{"date-parts":[[2010,3,12]],"date-time":"2010-03-12T13:31:47Z","timestamp":1268400707000},"page":"36-48","source":"Crossref","is-referenced-by-count":36,"title":["Parameterized Complexity of Generalized Vertex Cover Problems"],"prefix":"10.1007","author":[{"given":"Jiong","family":"Guo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Wernicke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"5_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: Proc. ALENEX 2004, pp. 62\u201369. ACM\/SIAM (2004)"},{"issue":"4","key":"5_CR2","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00453-001-0116-5","volume":"33","author":"J. Alber","year":"2002","unstructured":"Alber, J., Bodlaender, H.L., Fernau, H., Kloks, T., Niedermeier, R.: Fixed parameter algorithms for Dominating Set and related problems on planar graphs. Algorithmica\u00a033(4), 461\u2013493 (2002)","journal-title":"Algorithmica"},{"issue":"2","key":"5_CR3","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.dam.2004.01.013","volume":"145","author":"J. Alber","year":"2005","unstructured":"Alber, J., Dorn, F., Niedermeier, R.: Experimental evaluation of a tree decomposition based algorithm for Vertex Cover on planar graphs. Discrete Applied Mathematics\u00a0145(2), 219\u2013231 (2005)","journal-title":"Discrete Applied Mathematics"},{"key":"5_CR4","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.jalgor.2004.03.005","volume":"52","author":"J. Alber","year":"2004","unstructured":"Alber, J., Fernau, H., Niedermeier, R.: Parameterized complexity: exponential speed-up for planar graph problems. Journal of Algorithms\u00a052, 26\u201356 (2004)","journal-title":"Journal of Algorithms"},{"key":"5_CR5","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0012-365X(00)00199-0","volume":"229","author":"J. Alber","year":"2001","unstructured":"Alber, J., Gramm, J., Niedermeier, R.: Faster exact algorithms for hard problems: a parameterized point of view. Discrete Mathematics\u00a0229, 3\u201327 (2001)","journal-title":"Discrete Mathematics"},{"issue":"6","key":"5_CR6","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/0020-0190(93)90072-H","volume":"47","author":"E.M. Arkin","year":"1993","unstructured":"Arkin, E.M., Halld\u00f3rsson, M.M., Hassin, R.: Approximating the tree and tour covers of a graph. Information Processing Letters\u00a047(6), 275\u2013282 (1993)","journal-title":"Information Processing Letters"},{"key":"5_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/3-540-36136-7_40","volume-title":"Algorithms and Computation","author":"V. Arvind","year":"2002","unstructured":"Arvind, V., Raman, V.: Approximation algorithms for some parameterized counting problems. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol.\u00a02518, pp. 453\u2013464. Springer, Heidelberg (2002)"},{"issue":"3","key":"5_CR8","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0020-0190(97)00213-5","volume":"65","author":"R. Balasubramanian","year":"1998","unstructured":"Balasubramanian, R., Fellows, M.R., Raman, V.: An improved fixed-parameter algorithm for Vertex Cover. Information Processing Letters\u00a065(3), 163\u2013168 (1998)","journal-title":"Information Processing Letters"},{"issue":"6","key":"5_CR9","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/S0020-0190(02)00434-9","volume":"85","author":"M. Bl\u00e4ser","year":"2003","unstructured":"Bl\u00e4ser, M.: Computing small partial coverings. Information Processing Letters\u00a085(6), 327\u2013331 (2003)","journal-title":"Information Processing Letters"},{"key":"5_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1007\/BFb0028569","volume-title":"STACS 98","author":"N.H. Bshouty","year":"1998","unstructured":"Bshouty, N.H., Burroughs, L.: Massaging a linear programming solution to give a 2-approximation for a generalization of the Vertex Cover problem. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol.\u00a01373, pp. 298\u2013308. Springer, Heidelberg (1998)"},{"issue":"4","key":"5_CR11","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1016\/S0022-0000(03)00074-6","volume":"67","author":"L. Cai","year":"2003","unstructured":"Cai, L., Juedes, D.: On the existence of subexponential parameterized algorithms. Journal of Computer and System Sciences\u00a067(4), 789\u2013807 (2003)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"5_CR12","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/j.ipl.2004.10.003","volume":"93","author":"L.S. Chandran","year":"2005","unstructured":"Chandran, L.S., Grandoni, F.: Refined memorisation for Vertex Cover. Information Processing Letters\u00a093(3), 125\u2013131 (2005)","journal-title":"Information Processing Letters"},{"issue":"4","key":"5_CR13","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1016\/S0022-0000(03)00075-8","volume":"67","author":"J. Cheetham","year":"2003","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\u00a067(4), 691\u2013706 (2003)","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR14","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J. Chen","year":"2001","unstructured":"Chen, J., Kanj, I.A., Jia, W.: Vertex Cover: further observations and further improvements. Journal of Algorithms\u00a041, 280\u2013301 (2001)","journal-title":"Journal of Algorithms"},{"key":"5_CR15","first-page":"481","volume-title":"Proc. 43rd FOCS","author":"J. Chuzhoy","year":"2002","unstructured":"Chuzhoy, J., Naor, J.S.: Covering problems with hard capacities. In: Proc. 43rd FOCS, pp. 481\u2013489. IEEE Computer Society Press, Los Alamitos (2002)"},{"key":"5_CR16","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"5_CR17","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":"5_CR18","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"S.E. Dreyfus","year":"1972","unstructured":"Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks\u00a01, 195\u2013207 (1972)","journal-title":"Networks"},{"key":"5_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1007\/978-3-540-45078-8_44","volume-title":"Algorithms and Data Structures","author":"M.R. Fellows","year":"2003","unstructured":"Fellows, M.R.: New directions and new challenges in algorithm design and complexity, parameterized. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol.\u00a02748, pp. 505\u2013520. Springer, Heidelberg (2003)"},{"key":"5_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/3-540-45061-0_15","volume-title":"Automata, Languages and Programming","author":"R. Gandhi","year":"2003","unstructured":"Gandhi, R., Halperin, E., Khuller, S., Kortsarz, G., Srinivasan, A.: An improved approximation algorithm for Vertex Cover with hard capacities. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 164\u2013175. Springer, Heidelberg (2003)"},{"key":"5_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/3-540-48224-5_19","volume-title":"Automata, Languages and Programming","author":"R. Gandhi","year":"2001","unstructured":"Gandhi, R., Khuller, S., Srinivasan, A.: Approximation algorithms for partial covering problems. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, pp. 225\u2013236. Springer, Heidelberg (2001)"},{"issue":"1","key":"5_CR22","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S0196-6774(03)00053-1","volume":"48","author":"S. Guha","year":"2003","unstructured":"Guha, S., Hassin, R., Khuller, S., Or, E.: Capacitated vertex covering. Journal of Algorithms\u00a048(1), 257\u2013270 (2003)","journal-title":"Journal of Algorithms"},{"issue":"3","key":"5_CR23","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/s00453-003-1071-0","volume":"38","author":"J. K\u00f6nemann","year":"2004","unstructured":"K\u00f6nemann, J., Konjevod, G., Parekh, O., Sinha, A.: Improved approximations for tour and tree covers. Algorithmica\u00a038(3), 441\u2013449 (2004)","journal-title":"Algorithmica"},{"key":"5_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/978-3-540-28629-5_4","volume-title":"Mathematical Foundations of Computer Science 2004","author":"R. Niedermeier","year":"2004","unstructured":"Niedermeier, R.: Ubiquitous parameterization\u2014invitation to fixed-parameter algorithms. In: Fiala, J., Koubek, V., Kratochv\u00edl, J. (eds.) MFCS 2004. LNCS, vol.\u00a03153, pp. 84\u2013103. Springer, Heidelberg (2004)"},{"key":"5_CR25","doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, forthcoming (2005)","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"5_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/3-540-49116-3_53","volume-title":"STACS 99","author":"R. Niedermeier","year":"1999","unstructured":"Niedermeier, R., Rossmanith, P.: Upper bounds for vertex cover further improved. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol.\u00a01563, pp. 561\u2013570. Springer, Heidelberg (1999)"},{"key":"5_CR27","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0020-0190(00)00004-1","volume":"73","author":"R. Niedermeier","year":"2000","unstructured":"Niedermeier, R., Rossmanith, P.: A general method to speed up fixed-parametertractable algorithms. Information Processing Letters\u00a073, 125\u2013129 (2000)","journal-title":"Information Processing Letters"},{"issue":"2","key":"5_CR28","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/S0196-6774(03)00005-1","volume":"47","author":"R. Niedermeier","year":"2003","unstructured":"Niedermeier, R., Rossmanith, P.: On efficient fixed-parameter algorithms for Weighted Vertex Cover. Journal of Algorithms\u00a047(2), 63\u201377 (2003)","journal-title":"Journal of Algorithms"},{"key":"5_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/3-540-44634-6_8","volume-title":"Algorithms and Data Structures","author":"N. Nishimura","year":"2001","unstructured":"Nishimura, N., Ragde, P., Thilikos, D.M.: Fast fixed-parameter tractable algorithms for nontrivial generalizations of Vertex Cover. In: Dehne, F., Sack, J.-R., Tamassia, R. (eds.) WADS 2001. LNCS, vol.\u00a02125, pp. 75\u201386. Springer, Heidelberg (2001)"},{"key":"5_CR30","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 FPTalgorithms\u2014the 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)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11534273_5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:10:04Z","timestamp":1605643804000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11534273_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540281016","9783540317111"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/11534273_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}