{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T15:48:27Z","timestamp":1649000907215},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,3,21]],"date-time":"2017-03-21T00:00:00Z","timestamp":1490054400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2017,11]]},"DOI":"10.1007\/s10878-017-0127-z","type":"journal-article","created":{"date-parts":[[2017,3,21]],"date-time":"2017-03-21T08:47:15Z","timestamp":1490086035000},"page":"1052-1059","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximation for vertex cover in \n                $$\\beta $$\n                \n                    \n                                    \n                        \u03b2\n                    \n                \n            -conflict graphs"],"prefix":"10.1007","volume":"34","author":[{"given":"Dongjing","family":"Miao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhipeng","family":"Cai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weitian","family":"Tong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianzhong","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,3,21]]},"reference":[{"key":"127_CR1","first-page":"27","volume":"25","author":"R Bar-Yehuda","year":"1985","unstructured":"Bar-Yehuda R, Even S (1985) A local-ratio theorem for approximating the weighted vertex cover problem. Ann Discrete Math 25:27\u201346","journal-title":"Ann Discrete Math"},{"issue":"4","key":"127_CR2","doi-asserted-by":"crossref","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 PJ (2003) Solving large FPT problems on coarse-grained parallel machines. J Comput Syst Sci 67(4):691\u2013706","journal-title":"J Comput Syst Sci"},{"issue":"40\u201342","key":"127_CR3","doi-asserted-by":"crossref","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J Chen","year":"2010","unstructured":"Chen J, Kanj IA, Xia G (2010) Improved upper bounds for vertex cover. Theor Comput Sci 411(40\u201342):3736\u20133756","journal-title":"Theor Comput Sci"},{"key":"127_CR4","doi-asserted-by":"crossref","unstructured":"Dinur I, Safra S (2005) On the hardness of approximating minimum vertex cover. Ann Math 162(1):439\u2013485","DOI":"10.4007\/annals.2005.162.439"},{"issue":"1\u20132","key":"127_CR5","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"RG Downey","year":"1995","unstructured":"Downey RG, Fellows MR (1995) Fixed-parameter tractability and completeness II: on completeness for w[1]. Theor Comput Sci 141(1\u20132):109\u2013131","journal-title":"Theor Comput Sci"},{"issue":"6","key":"127_CR6","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1016\/S1007-0214(10)70116-4","volume":"15","author":"J Fang","year":"2010","unstructured":"Fang J, Huang Z (2010) Reasoning with inconsistent ontologies. Tsinghua Sci Technol 15(6):687\u2013691","journal-title":"Tsinghua Sci Technol"},{"issue":"2","key":"127_CR7","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F Gavril","year":"1972","unstructured":"Gavril F (1972) Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J Comput 1(2):180\u2013187","journal-title":"SIAM J Comput"},{"issue":"4","key":"127_CR8","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad J (2001) Some optimal inapproximability results. J ACM 48(4):798\u2013859","journal-title":"J ACM"},{"issue":"4","key":"127_CR9","doi-asserted-by":"crossref","first-page":"41:1","DOI":"10.1145\/1597036.1597045","volume":"5","author":"G Karakostas","year":"2009","unstructured":"Karakostas G (2009) A better approximation ratio for the vertex cover problem. ACM Trans Algorithms 5(4):41:1\u201341:8","journal-title":"ACM Trans Algorithms"},{"issue":"3","key":"127_CR10","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 (2008) Vertex cover might be hard to approximate to within \n                        $$2-\\epsilon $$\n                        \n                            \n                                            \n                                \n                                    2\n                                    -\n                                    \u03f5\n                                \n                            \n                        \n                    . J Comput Syst Sci 74(3):335\u2013349","journal-title":"J Comput Syst Sci"},{"key":"127_CR11","doi-asserted-by":"crossref","unstructured":"Kuhn F, Mastrolilli M (2011) Vertex cover in graphs with locally few colors. In: Proceedings of the 38th international colloquim conference on automata, languages and programming, Vol Part I. ICALP\u201911. Springer, Berlin, pp 498\u2013509","DOI":"10.1007\/978-3-642-22006-7_42"},{"issue":"2","key":"127_CR12","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/j.ipl.2005.09.006","volume":"97","author":"G Lin","year":"2006","unstructured":"Lin G, Cai Z, Lin D (2006) Vertex covering by paths on trees with its applications in machine translation. Inf Process Lett 97(2):73\u201381","journal-title":"Inf Process Lett"},{"issue":"1","key":"127_CR13","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1109\/TST.2014.6733206","volume":"19","author":"Y Liu","year":"2014","unstructured":"Liu Y, Wu B, Wang H, Ma P (2014) Bpgm: a big graph mining tool. Tsinghua Sci Technol 19(1):33\u201338","journal-title":"Tsinghua Sci Technol"},{"key":"127_CR14","doi-asserted-by":"crossref","unstructured":"Miao D, Li J, Liu X, Gao H (2015) Vertex cover in conflict graphs: complexity and a near optimal approximation. In: Proceedings of the 9th international conference on combinatorial optimization and applications, vol 9486. COCOA 2015, New York. Springer, New York, Inc, pp 395\u2013408","DOI":"10.1007\/978-3-319-26626-8_29"},{"issue":"1","key":"127_CR15","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/BF00290149","volume":"22","author":"B Monien","year":"1985","unstructured":"Monien B, Speckenmeyer E (1985) Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Inform 22(1):115\u2013123","journal-title":"Acta Inform"},{"issue":"1","key":"127_CR16","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"GL Nemhauser","year":"1975","unstructured":"Nemhauser GL, Trotter LE Jr (1975) Vertex packings: structural properties and algorithms. Math Program 8(1):232\u2013248","journal-title":"Math Program"},{"issue":"5","key":"127_CR17","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0020-0190(82)90022-9","volume":"14","author":"CD Savage","year":"1982","unstructured":"Savage CD (1982) Depth-first search and the vertex cover problem. Inf Process Lett 14(5):233\u2013237","journal-title":"Inf Process Lett"},{"key":"127_CR18","volume-title":"Approximation algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani VV (2001) Approximation algorithms. Springer, new york"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-017-0127-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0127-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0127-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,10,9]],"date-time":"2017-10-09T11:42:30Z","timestamp":1507549350000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-017-0127-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,21]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["127"],"URL":"https:\/\/doi.org\/10.1007\/s10878-017-0127-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3,21]]}}}