{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T11:49:27Z","timestamp":1649159367771},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2014,1,8]],"date-time":"2014-01-08T00:00:00Z","timestamp":1389139200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sci. China Inf. Sci."],"published-print":{"date-parts":[[2014,7]]},"DOI":"10.1007\/s11432-013-4845-2","type":"journal-article","created":{"date-parts":[[2014,1,8]],"date-time":"2014-01-08T04:41:16Z","timestamp":1389156076000},"page":"1-12","source":"Crossref","is-referenced-by-count":0,"title":["On the parameterized vertex cover problem for graphs with perfect matching"],"prefix":"10.1007","volume":"57","author":[{"given":"JianXin","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"WenJun","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ShaoHua","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JianEr","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,1,8]]},"reference":[{"key":"4845_CR1","volume-title":"Computers and Intractability: a Guide to the Thoery of NP-completeness","author":"M R Garey","year":"1979","unstructured":"Garey M R, Johnson D S. Computers and Intractability: a Guide to the Thoery of NP-completeness. New York: Freeman, W. H. and Company, 1979"},{"key":"4845_CR2","volume-title":"Algorithms for building multiple sequence alignments and evolutionary trees","author":"C Roth-Korostensky","year":"2000","unstructured":"Roth-Korostensky C. Algorithms for building multiple sequence alignments and evolutionary trees. Dissertation for Doctoral Degree. ETH Z\u00fcrich 13550, 2000"},{"key":"4845_CR3","volume-title":"Resolving conflicts from problems in computational biology","author":"U Stege","year":"2000","unstructured":"Stege U. Resolving conflicts from problems in computational biology. Dissertation for Doctoral Degree. ETH Z\u00fcrich 13364, 2000"},{"key":"4845_CR4","first-page":"94","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"D Hochbaum","year":"1997","unstructured":"Hochbaum D. Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems. In: Hochbaum D, ed. Approximation Algorithms for NP-Hard Problems. Boston: PWS Publishing Company, 1997. 94\u2013143"},{"key":"4845_CR5","doi-asserted-by":"crossref","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. Inf Process Lett, 1998, 65: 163\u2013168","journal-title":"Inf Process Lett"},{"key":"4845_CR6","doi-asserted-by":"crossref","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. J Algorithm, 2001, 41: 280\u2013301","journal-title":"J Algorithm"},{"key":"4845_CR7","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/978-1-4612-2566-9_7","volume-title":"Feasible Mathematics II","author":"R G Downey","year":"1995","unstructured":"Downey R G, Fellows M R. Parameterized computational feasibility. In: Clote P, Remmel J, eds. Feasible Mathematics II. Boston: Birkhauser, 1995. 219\u2013244"},{"key":"4845_CR8","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1007\/3-540-49116-3_53","volume":"1563","author":"R Niedermeier","year":"1999","unstructured":"Niedermeier R, Rossmanith P. Upper bounds for vertex cover further improved. Lect Note Comput Sci, 1999, 1563: 561\u2013570","journal-title":"Lect Note Comput Sci"},{"key":"4845_CR9","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot S, Regev O. Vertex cover might be hard to approximate to within 2 \u2212 \u03b5. J Comput Syst Sci, 2008, 74: 335\u2013349","journal-title":"J Comput Syst Sci"},{"key":"4845_CR10","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1007\/11821069_21","volume":"4162","author":"J Chen","year":"2006","unstructured":"Chen J, Kanj I A, Xia G. Improved parameterized upper bounds for vertex cover. Lect Note Comput Sci, 2006, 4162: 238\u2013249","journal-title":"Lect Note Comput Sci"},{"key":"4845_CR11","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1016\/S0022-0000(03)00074-6","volume":"67","author":"L Cai","year":"2003","unstructured":"Cai L, Juedes D W. On the existence of subexponential parameterized algorithms. J Comput Syst Sci, 2003, 67: 789\u2013807","journal-title":"J Comput Syst Sci"},{"key":"4845_CR12","doi-asserted-by":"crossref","first-page":"1672","DOI":"10.1016\/j.artint.2011.03.003","volume":"175","author":"S Cai","year":"2001","unstructured":"Cai S, Su K, Sattar A. Local search with edge weighting and configuration checking heuristics for minimum vertex cover. Artif Intell, 2001, 175: 1672\u20131696","journal-title":"Artif Intell"},{"key":"4845_CR13","volume-title":"Cliques, Coloring, and Satisfiability: second DIMACS Implementation Challenge","year":"1996","unstructured":"Johnson D S, Trick M A, eds. Cliques, Coloring, and Satisfiability: second DIMACS Implementation Challenge. American Mathematical Society, 1996. Benchmarks available at ftp:\/\/dimacs.rutgers.edu\/pub\/challenges"},{"key":"4845_CR14","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1016\/j.artint.2007.04.001","volume":"171","author":"K Xu","year":"2007","unstructured":"Xu K, Boussemart F, Hemery F, et al. Random constraint satisfaction: easy generation of hard (satisfiable) instances. Artif Intell, 2007, 171: 514\u2013534. Benchmarks available at http:\/\/www.nlsde.buaa.edu.cn\/~kexu\/benchmarks\/graphbenchmarks.htm","journal-title":"Artif Intell"},{"key":"4845_CR15","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/j.tcs.2004.12.034","volume":"337","author":"J Chen","year":"2005","unstructured":"Chen J, Kanj I A. On approximating minimum vertex cover for graphs with perfect matching. Theor Comput Sci, 2005, 337: 305\u2013318","journal-title":"Theor Comput Sci"},{"issue":"8","key":"4845_CR16","doi-asserted-by":"crossref","first-page":"2405","DOI":"10.1093\/ietisy\/e89-d.8.2405","volume":"E89-D","author":"T Imamura","year":"2009","unstructured":"Imamura T, Iwama K, Tsukiji T. Approximated vertex cover for graphs with perfect matchings. Trans Inf Syst, 2009, E89-D(8): 2405\u20132410","journal-title":"Trans Inf Syst"},{"key":"4845_CR17","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1016\/j.dam.2006.04.039","volume":"155","author":"M Chlebik","year":"2007","unstructured":"Chlebik M, Chlebikova J. Minimum 2sat-deletion inapproximability results and relations to minimum vertex cover. Discrete Appl Math, 2007, 155: 172\u2013179","journal-title":"Discrete Appl Math"},{"key":"4845_CR18","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1006\/jagm.1998.0996","volume":"3","author":"M Mahajan","year":"1999","unstructured":"Mahajan M, Raman V. Parametrizing above guaranteed values: maxSat and maxCut. J Algorithm, 1999 3: 335\u2013354","journal-title":"J Algorithm"},{"key":"4845_CR19","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1007\/11847250_4","volume":"4169","author":"M Mahajan","year":"2006","unstructured":"Mahajan M, Raman V, Sikdar S. Parameterizing MAX SNP problems above guaranteed values. Lect Note Comput Sci, 2006, 4169: 38\u201349","journal-title":"Lect Note Comput Sci"},{"key":"4845_CR20","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/j.jcss.2008.08.004","volume":"75","author":"M Mahajan","year":"2009","unstructured":"Mahajan M, Raman V, Sikdar S. Parameterizing above or below guaranteed values. J Comput Syst Sci, 2009, 75: 137\u2013153","journal-title":"J Comput Syst Sci"},{"key":"4845_CR21","first-page":"551","volume-title":"Almost 2-SAT is Fixed-Parameter Tractable","author":"I Razgon","year":"2008","unstructured":"Razgon I, O\u2019Sullivan B. Almost 2-SAT is Fixed-Parameter Tractable. Berlin: Springer, 2008. 551\u2013562"},{"key":"4845_CR22","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1007\/978-3-540-77120-3_25","volume":"4835","author":"S Mishra","year":"2007","unstructured":"Mishra S, Raman V, Saurabh S, et al. The complexity of finding subgraphs whose matching number equals the vertex cover number. Lect Note Comput Sci, 2007, 4835: 268\u2013279","journal-title":"Lect Note Comput Sci"},{"key":"4845_CR23","doi-asserted-by":"crossref","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. Oper Res Lett, 2004, 32: 299\u2013301","journal-title":"Oper Res Lett"},{"key":"4845_CR24","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0012-365X(79)90066-9","volume":"27","author":"R Deming","year":"1979","unstructured":"Deming R. Independence numbers of graphs\u2014an extension of the K\u00f6nig-Egerv\u00e1ry theorem. Discrete Math, 1979, 27: 23\u201333","journal-title":"Discrete Math"},{"key":"4845_CR25","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/BF01305952","volume":"14","author":"V Vazirani","year":"1994","unstructured":"Vazirani V. A theory of alternating paths and blossoms for proving correctness of the O( $\\sqrt V $ E) general graph maximum matching algorithm. Combinatorica, 1994, 14: 71\u2013109","journal-title":"Combinatorica"},{"key":"4845_CR26","first-page":"842","volume-title":"Proceedings of 17th Annual ACM-SIAM Sympothesis on Discrete Algorithms (SODA)","author":"E Korach","year":"2006","unstructured":"Korach E, Nguyen T, Peis B. Subgraph characterization of red\/blue-split graph and K\u00f6nig-Egerv\u00e1ry graphs. In: Proceedings of 17th Annual ACM-SIAM Sympothesis on Discrete Algorithms (SODA), 2006. 842\u2013850"},{"key":"4845_CR27","volume-title":"Introduction to Algorithms","author":"T Cormen","year":"2011","unstructured":"Cormen T, Teiserson C, Rivest R, et al. Introduction to Algorithms. 2nd ed. Cambridge: MIT Press, 2011","edition":"2nd ed."},{"key":"4845_CR28","doi-asserted-by":"crossref","first-page":"836","DOI":"10.1007\/978-3-540-92182-0_73","volume":"5369","author":"S Mishra","year":"2008","unstructured":"Mishra S, Raman V, Saurabh S, et al. K\u00f6nig deletion sets and vertex covers above the matching size. Lect Note Comput Sci, 2008, 5369: 836\u2013847","journal-title":"Lect Note Comput Sci"},{"key":"4845_CR29","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1007\/978-3-642-23719-5_33","volume":"6942","author":"V Raman","year":"2011","unstructured":"Raman V, Ramanujan S, Saurabh S. Paths, flowers and vertex cover. Lect Note Comput Sci, 2011, 6942: 382\u2013393","journal-title":"Lect Note Comput Sci"},{"key":"4845_CR30","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-642-28050-4_1","volume":"7112","author":"M Cygan","year":"2011","unstructured":"Cygan M, Pilipczuk M, Pilipczuk M, et al. On multiway cut parameterized above lower bounds. Lect Note Comput Sci, 2011, 7112: 1\u201312","journal-title":"Lect Note Comput Sci"},{"key":"4845_CR31","first-page":"338","volume-title":"Proceedings of 29th International Symposium on Theoretical Aspects of Computer Science","author":"S Narayanaswamy","year":"2011","unstructured":"Narayanaswamy S, Raman V, Ramanujan S, et al. LP can be a cure for parameterized problems. In: Proceedings of 29th International Symposium on Theoretical Aspects of Computer Science, 2011. 338\u2013349"}],"container-title":["Science China Information Sciences"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11432-013-4845-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11432-013-4845-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11432-013-4845-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T15:37:51Z","timestamp":1559403471000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11432-013-4845-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1,8]]},"references-count":31,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2014,7]]}},"alternative-id":["4845"],"URL":"https:\/\/doi.org\/10.1007\/s11432-013-4845-2","relation":{},"ISSN":["1674-733X","1869-1919"],"issn-type":[{"value":"1674-733X","type":"print"},{"value":"1869-1919","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1,8]]}}}