{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T16:30:41Z","timestamp":1761323441846},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540377917"},{"type":"electronic","value":"9783540377931"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11821069_21","type":"book-chapter","created":{"date-parts":[[2006,8,25]],"date-time":"2006-08-25T10:25:12Z","timestamp":1156501512000},"page":"238-249","source":"Crossref","is-referenced-by-count":62,"title":["Improved Parameterized Upper Bounds for Vertex Cover"],"prefix":"10.1007","author":[{"given":"Jianer","family":"Chen","sequence":"first","affiliation":[]},{"given":"Iyad A.","family":"Kanj","sequence":"additional","affiliation":[]},{"given":"Ge","family":"Xia","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"21_CR1","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., Raman, V.: An improved fixed parameter algorithm for Vertex Cover. Information Processing Letters\u00a065, 163\u2013168 (1998)","journal-title":"Information Processing Letters"},{"key":"21_CR2","first-page":"27","volume":"25","author":"R. Bar-Yehuda","year":"1985","unstructured":"Bar-Yehuda, R., Even, S.: A local-ratio theorem for approximating the Weighted Vertex Cover problem. Annals of Discrete Mathematics\u00a025, 27\u201346 (1985)","journal-title":"Annals of Discrete Mathematics"},{"key":"21_CR3","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1137\/0222038","volume":"22","author":"J. Buss","year":"1993","unstructured":"Buss, J., Goldsmith, J.: Nondeterminism within P. SIAM Journal on Computing\u00a022, 560\u2013572 (1993)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"21_CR4","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"},{"key":"21_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-540-28639-4_6","volume-title":"Parameterized and Exact Computation","author":"L. Sunil Chandran","year":"2004","unstructured":"Sunil Chandran, L., Grandoni, F.: Refined memorisation for vertex cover. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol.\u00a03162, pp. 61\u201370. Springer, Heidelberg (2004)"},{"issue":"4","key":"21_CR6","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.: 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":"21_CR7","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., Jia, W.: Vertex cover: further observations and further improvements. Journal of Algorithms\u00a041, 280\u2013301 (2001)","journal-title":"Journal of Algorithms"},{"key":"21_CR8","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1002\/1097-0037(200007)35:4<253::AID-NET3>3.0.CO;2-K","volume":"35","author":"J. Chen","year":"2000","unstructured":"Chen, J., Liu, L., Jia, W.: Improvement on Vertex Cover for low degree graphs. Networks\u00a035, 253\u2013259 (2000)","journal-title":"Networks"},{"key":"21_CR9","unstructured":"Chlebik, M., Chlebikova, J.: Crown reductions for the minimum weighted vertex cover problem. Electronic Colloquium on Computational Complexity, Report No. 101 (2004)"},{"key":"21_CR10","first-page":"161","volume":"87","author":"R. Downey","year":"1992","unstructured":"Downey, R., Fellows, M.: Fixed-parameter tractability and completeness. Congressus Numerantium\u00a087, 161\u2013187 (1992)","journal-title":"Congressus Numerantium"},{"key":"21_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R. Downey","year":"1999","unstructured":"Downey, R., Fellows, M.: Parameterized Complexity. Springer, New York (1999)"},{"key":"21_CR12","first-page":"83","volume":"19","author":"C. Ebengger","year":"1984","unstructured":"Ebengger, C., Hammer, P., de Werra, D.: Pseudo-boolean functions and stability of graphs. Annals of Discrete Mathematics\u00a019, 83\u201398 (1984)","journal-title":"Annals of Discrete Mathematics"},{"key":"21_CR13","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.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":"21_CR14","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, New York (1979)"},{"key":"21_CR15","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: Which problems have strongly exponential complexity? Journal of Computer and System Sciences\u00a063, 512\u2013530 (2001)","journal-title":"Journal of Computer and System Sciences"},{"key":"21_CR16","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G. Nemhauser","year":"1975","unstructured":"Nemhauser, G., Trotter, L.: Vertex packing: structural properties and algorithms. Mathematical Programming\u00a08, 232\u2013248 (1975)","journal-title":"Mathematical Programming"},{"key":"21_CR17","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":"21_CR18","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, 63\u201377 (2003)","journal-title":"Journal of Algorithms"},{"key":"21_CR19","first-page":"425","volume":"6","author":"J.M. Robson","year":"1977","unstructured":"Robson, J.M.: Algorithms for maximum independent set. Journal of Algorithms\u00a06, 425\u2013440 (1977)","journal-title":"Journal of Algorithms"},{"key":"21_CR20","unstructured":"Stege, U., Fellows, M.: An improved fixed-parameter-tractable algorithm for Vertex Cover. Technical Report 318, Department of Computer Science, ETH Z\u00fcrich (April 1999)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11821069_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:30:35Z","timestamp":1619508635000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11821069_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540377917","9783540377931"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/11821069_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}