{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:15:56Z","timestamp":1725664556908},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540613329"},{"type":"electronic","value":"9783540684619"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61332-3_167","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:34:37Z","timestamp":1330274077000},"page":"333-342","source":"Crossref","is-referenced-by-count":8,"title":["Improved non-approximability results for vertex cover with density constraints"],"prefix":"10.1007","author":[{"given":"Andrea E. F.","family":"Clementi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luca","family":"Trevisan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,4]]},"reference":[{"key":"35_CR1","doi-asserted-by":"crossref","unstructured":"S. Arora, D. Karger, and M. Karpinski. Polynomial time approximation schemes for dense instances of graph problems. In Proceedings of the 27th ACM Symposium on Theory of Computing, pages 284\u2013293, 1995.","DOI":"10.1145\/225058.225140"},{"key":"35_CR2","doi-asserted-by":"crossref","unstructured":"S. Arora and S. Safra. Probabilistic checking of proofs; a new characterization of NP. In Proceedings of 33rd Symposium on Foundations of Computer Science, pages 2\u201313, 1992.","DOI":"10.1109\/SFCS.1992.267824"},{"key":"35_CR3","unstructured":"M. Bellare, O. Goldreich, and M. Sudan. Free bits, PCP's and non-approximability \u2014 towards tight results (3rd version). Technical Report TR95-24, Electronic Colloquium on Computational Complexity, 1995. Extended abstract in Proc. of FOCS'95."},{"key":"35_CR4","doi-asserted-by":"crossref","unstructured":"P. Berman and T. Fujito. On the approximation properties of the independent set problem in degree 3 graphs. In Proceedings of the 4th Workshop on Algorithms and Data Structures, pages 449\u2013460. LNCS 955, Springer-Verlag, 1995.","DOI":"10.1007\/3-540-60220-8_84"},{"key":"35_CR5","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0020-0190(89)90039-2","volume":"32","author":"M. Bern","year":"1989","unstructured":"M. Bern and P. Plassmann. The steiner tree problem with edge lengths 1 and 2. Information Processing Letters, 32:171\u2013176, 1989.","journal-title":"Information Processing Letters"},{"key":"35_CR6","doi-asserted-by":"crossref","unstructured":"A.E.F. Clementi and L. Trevisan. Improved non-approximability results for vertex cover with density constraints. Technical Report TR 96-16, Electronic Colloquium on Computational Complexity, 1996.","DOI":"10.1007\/3-540-61332-3_167"},{"key":"35_CR7","unstructured":"P. Crescenzi and V. Kann. A compendium of NP optimization problems. Technical Report TR SI-95\/02, Universit\u00e0 di Roma \u201cLa Sapienza\u201d, Dipartimento di Scienze dell'Informazione, 1995. Updated on-line version is available at the URL http:\/\/www.nada.kth.se\/\u223cviggo\/problemlist\/compendium.html."},{"key":"35_CR8","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/0890-5401(91)90025-W","volume":"93","author":"P. Crescenzi","year":"1991","unstructured":"P. Crescenzi and A. Panconesi. Completeness in approximation classes. Information and Computation, 93:241\u2013262, 1991. Preliminary version in Proc. of FCT'89.","journal-title":"Information and Computation"},{"key":"35_CR9","doi-asserted-by":"crossref","unstructured":"U. Feige. A threshold of ln n for approximating set cover. In Proceedings of the 28th ACM Symposium on Theory of Computing, 1996. To appear.","DOI":"10.1145\/237814.237977"},{"key":"35_CR10","doi-asserted-by":"crossref","unstructured":"U. Feige, S. Goldwasser, L. Lovasz, S. Safra, and M. Szegedy. Approximating clique is almost NP-complete. In Proceedings of 32nd Symposium on Foundations of Computer Science, pages 2\u201312, 1991.","DOI":"10.1109\/SFCS.1991.185341"},{"key":"35_CR11","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M. R. Garey","year":"1976","unstructured":"M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, 1:237\u2013267, 1976.","journal-title":"Theoretical Computer Science"},{"key":"35_CR12","unstructured":"M.R. Garey and D.S. Johnson. Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman, 1979."},{"key":"35_CR13","unstructured":"F. Gavril. Manuscript cited in [12], 1974."},{"key":"35_CR14","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad. Testing of the long code and hardness for clique. In Proceedings of the 28th ACM Symposium on Theory of Computing, 1996. To appear.","DOI":"10.1145\/237814.237820"},{"key":"35_CR15","doi-asserted-by":"crossref","unstructured":"R.M. Karp. Reducibility among combinatorial problems. In R.E. Miller and J.W. Thatcher, editors, Complexity of Computer Computations, pages 85\u2013103. Plenum Press, 1972.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"35_CR16","doi-asserted-by":"crossref","unstructured":"S. Khanna, R. Motwani, M. Sudan, and U. Vazirani. On syntactic versus computational views of approximability. In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, pages 819\u2013830, 1994.","DOI":"10.1109\/SFCS.1994.365712"},{"issue":"3","key":"35_CR17","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/BF02126799","volume":"8","author":"A. Lubotzky","year":"1988","unstructured":"A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3):261\u2013277, 1988.","journal-title":"Combinatorica"},{"key":"35_CR18","doi-asserted-by":"crossref","unstructured":"B. Monien and E. Speckenmeyer. Some further approximation algorithms for the vertex cover problem. In Proceedings of CAAP83, pages 341\u2013349. LNCS 159, Springer Verlag, 1983.","DOI":"10.1007\/3-540-12727-5_21"},{"key":"35_CR19","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. H. Papadimitriou","year":"1991","unstructured":"C. H. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. Journal of Computer and System Sciences, 43:425\u2013440, 1991. Preliminary version in Proc. of STOC'88.","journal-title":"Journal of Computer and System Sciences"},{"key":"35_CR20","unstructured":"C.H. Papadimitriou. Computational Complexity. Addison-Wesley, 1993."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61332-3_167.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:05:36Z","timestamp":1605629136000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61332-3_167"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540613329","9783540684619"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-61332-3_167","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}