{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,23]],"date-time":"2025-12-23T10:00:29Z","timestamp":1766484029831,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540602200"},{"type":"electronic","value":"9783540447474"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60220-8_84","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:53:25Z","timestamp":1330278805000},"page":"449-460","source":"Crossref","is-referenced-by-count":53,"title":["On approximation properties of the Independent set problem for degree 3 graphs"],"prefix":"10.1007","author":[{"given":"Piotr","family":"Berman","sequence":"first","affiliation":[]},{"given":"Toshihiro","family":"Fujito","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"39_CR1","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy. Proof verification and intractability of approximation problems. In 33rd IEEE Symp. on Foundations of Computer Science, 1992.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"39_CR2","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"B.S. Baker. Approximation algorithms for NP-complete problems on planar graphs. Journal of the Association for Computing Machinery, 41:153\u2013180, 1994.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"39_CR3","unstructured":"R. Bar-Yehuda, D. Geiger, J. Naor and R. M. Roth. Approximation algorithms for the vertex feedback set problem with applications to constraint satisfaction and bayesian inference. In Proc. of the 5th Annual ACM-SIAM Symp. on Discrete Algorithms, pages 344\u2013354, 1994."},{"key":"39_CR4","unstructured":"P. Berman and M. F\u00fcrer. Approximating maximum independent set in bounded degree graphs. In Proc. of the 5th Annual ACM-SIAM Symp. on Discrete Algorithms, 1994."},{"key":"39_CR5","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1017\/S030500410002168X","volume":"37","author":"R.L. Brooks","year":"1941","unstructured":"R.L. Brooks. On coloring the nodes of a network. In Proc. Cambridge Philos. Soc., volume 37, pages 194\u2013197, 1941.","journal-title":"Proc. Cambridge Philos. Soc."},{"key":"39_CR6","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":"39_CR7","doi-asserted-by":"crossref","unstructured":"M.M. Halld\u00f3rsson and J. Radhakrishnan. Greed is good: Approximating independent sets in sparse and bounded-degree graphs. In Proc. of the 26th Annual ACM Symp. on Theory of Computing, 1994.","DOI":"10.1145\/195058.195221"},{"key":"39_CR8","doi-asserted-by":"crossref","unstructured":"M.M. Halld\u00f3rsson and J. Radhakrishnan. Improved approximations of independent sets in bounded-degree graphs. In SWAT 94, 6th Scandinavian Workshop on Algorithm Theory, 1994.","DOI":"10.1007\/3-540-58218-5_18"},{"key":"39_CR9","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"D.S. Hochbaum","year":"1983","unstructured":"D.S. Hochbaum. Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Applied Mathematics, 6:243\u2013254, 1983.","journal-title":"Discrete Applied Mathematics"},{"key":"39_CR10","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0020-0190(91)90246-E","volume":"37","author":"V. Kann","year":"1991","unstructured":"V. Kann. Maximum bounded 3-dimensional matching is MAX SNP-complete. Information Processing Letters, 37:27\u201335, 1991.","journal-title":"Information Processing Letters"},{"key":"39_CR11","doi-asserted-by":"crossref","unstructured":"S. Khanna, R. Motwani, M. Sudan and U. Vazirani. On syntactic versus computation views of approximability. In 35th IEEE Symp. on Foundations of Computer Science, pages 819\u2013830, 1994.","DOI":"10.1109\/SFCS.1994.365712"},{"key":"39_CR12","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0095-8956(75)90089-1","volume":"19","author":"L. Lov\u00e1sz","year":"1975","unstructured":"L. Lov\u00e1sz. Three short proofs in graph theory. Journal of Combinatorial Theory (B), 19:269\u2013271, 1975.","journal-title":"Journal of Combinatorial Theory (B)"},{"key":"39_CR13","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G.L. Nemhauser","year":"1975","unstructured":"G.L. Nemhauser and L.E. Trotter Jr.. Vertex packings: structural properties and algorithms. Mathematical Programming, 8:232\u2013248, 1975.","journal-title":"Mathematical Programming"},{"key":"39_CR14","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"C. Papadimitriou and M. Yannakakis. Optimization, approximation and complexity classes. Journal of Computer and System Sciences, 43:425\u2013440, 1991.","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60220-8_84.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:56:00Z","timestamp":1742597760000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60220-8_84"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602200","9783540447474"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-60220-8_84","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}