{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,3]],"date-time":"2025-06-03T13:28:20Z","timestamp":1748957300042},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540310006"},{"type":"electronic","value":"9783540314684"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11604686_30","type":"book-chapter","created":{"date-parts":[[2005,12,5]],"date-time":"2005-12-05T15:02:01Z","timestamp":1133794921000},"page":"341-350","source":"Crossref","is-referenced-by-count":16,"title":["Approximation Algorithms for the Weighted Independent Set Problem"],"prefix":"10.1007","author":[{"given":"Akihisa","family":"Kako","sequence":"first","affiliation":[]},{"given":"Takao","family":"Ono","sequence":"additional","affiliation":[]},{"given":"Tomio","family":"Hirata","sequence":"additional","affiliation":[]},{"given":"Magn\u00fas M.","family":"Halld\u00f3rsson","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"30_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric algorithms and combinatorial optimization","author":"M. Gr\u00f6tschel","year":"1993","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric algorithms and combinatorial optimization, 2nd edn. Springer, Heidelberg (1993)","edition":"2"},{"issue":"1","key":"30_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00020","volume":"4","author":"M.M. Halld\u00f3rsson","year":"2000","unstructured":"Halld\u00f3rsson, M.M.: Approximations of weighted independent set and hereditary subset problems. Journal of Graphs Algorithms and Applications\u00a04(1), 1\u201316 (2000)","journal-title":"Journal of Graphs Algorithms and Applications"},{"key":"30_CR3","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M.M.: Approximations of independent sets in graphs. In: Jansen, K., Rolim, J. (eds.) The First International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pp. 1\u201314 (1998)","DOI":"10.1007\/BFb0053959"},{"issue":"3","key":"30_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00003","volume":"1","author":"M.M. Halld\u00f3rsson","year":"1997","unstructured":"Halld\u00f3rsson, M.M., Lau, H.C.: Low-degree graph partitioning via local search with applications to constraint satisfaction, max cut, and 3-coloring. Journal of Graph Algorithms and Applications\u00a01(3), 1\u201313 (1997)","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"30_CR5","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF02523693","volume":"18","author":"M.M. Halld\u00f3rsson","year":"1997","unstructured":"Halld\u00f3rsson, M.M., Radhakrishnan, J.: Greed is good: Approximating independent sets in sparse and bounded-degree graphs. Algorithmica\u00a018, 145\u2013163 (1997)","journal-title":"Algorithmica"},{"issue":"4","key":"30_CR6","first-page":"475","volume":"1","author":"M.M. Halld\u00f3rsson","year":"1994","unstructured":"Halld\u00f3rsson, M.M., Radhakrishnan, J.: Improved approximations of independent sets in bounded-degree graphs via subgraph removal. Nordic Journal of Computing\u00a01(4), 475\u2013482 (1994)","journal-title":"Nordic Journal of Computing"},{"key":"30_CR7","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"D.S. Hochbaum","year":"1983","unstructured":"Hochbaum, D.S.: Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Applied Mathematics\u00a06, 243\u2013254 (1983)","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"30_CR8","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1145\/2402.322385","volume":"30","author":"D.W. Matula","year":"1983","unstructured":"Matula, D.W., Beck, L.L.: Smallest-last ordering and clustering and graph coloring algorithms. Journal of the Association for Computing Machinery\u00a030(2), 417\u2013427 (1983)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"30_CR9","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G.L. Nemhauser","year":"1975","unstructured":"Nemhauser, G.L., Trotter, L.E.: Vertex packing: Structural properties and algorithms. Mathematical Programming\u00a08, 232\u2013248 (1975)","journal-title":"Mathematical Programming"},{"key":"30_CR10","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/S0166-218X(02)00205-6","volume":"126","author":"S. Sakai","year":"2003","unstructured":"Sakai, S., Togasaki, M., Yamazaki, K.: A note on greedy algorithms for maximum weighted independent set problem. Discrete Applied Mathematics\u00a0126, 313\u2013322 (2003)","journal-title":"Discrete Applied Mathematics"},{"key":"30_CR11","volume-title":"Combinatorial optimization: polyhedra and efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial optimization: polyhedra and efficiency, vol.\u00a0A. Springer, Heidelberg (2003)"},{"key":"30_CR12","volume-title":"Approximation algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation algorithms. Springer, Heidelberg (2001)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11604686_30.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:04:26Z","timestamp":1619507066000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11604686_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540310006","9783540314684"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/11604686_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}