{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T20:17:28Z","timestamp":1770063448610,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":8,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540671817","type":"print"},{"value":"9783540465157","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/978-3-540-46515-7_16","type":"book-chapter","created":{"date-parts":[[2010,10,20]],"date-time":"2010-10-20T13:35:28Z","timestamp":1287581728000},"page":"194-200","source":"Crossref","is-referenced-by-count":28,"title":["Approximation Algorithms for Maximum Independent Set Problems and Fractional Coloring Problems on Unit Disk Graphs"],"prefix":"10.1007","author":[{"given":"Tomomi","family":"Matsui","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and intractability of approximation problems. In: Proc. 33rd IEEE Symposium on Foundations of Computer Science, pp. 13\u201322 (1992)","DOI":"10.1109\/SFCS.1992.267823"},{"key":"16_CR2","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"B.N. Clark","year":"1990","unstructured":"Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Mathematics\u00a086, 165\u2013177 (1990)","journal-title":"Discrete Mathematics"},{"key":"16_CR3","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"},{"key":"16_CR4","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M. Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica\u00a01, 169\u2013197 (1981)","journal-title":"Combinatorica"},{"key":"16_CR5","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E.L. Lawler","year":"1976","unstructured":"Lawler, E.L.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York (1976)"},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/net.3230250205","volume":"25","author":"M.V. Marathe","year":"1995","unstructured":"Marathe, M.V., Breu, H., Hunt III, H.B., Ravi, S.S., Rosenkrantz, D.S.: Simple heuristics for unit disk graphs. Networks\u00a025, 59\u201368 (1995)","journal-title":"Networks"},{"key":"16_CR7","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1287\/opre.34.2.250","volume":"34","author":"E. Tardos","year":"1986","unstructured":"Tardos, E.: A strongly polynomial algorithm to solve combinatorial linear programs. Operations Research\u00a034, 250\u2013256 (1986)","journal-title":"Operations Research"},{"key":"16_CR8","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/0206036","volume":"6","author":"S. Tsukiyama","year":"1977","unstructured":"Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. on Computing\u00a06, 505\u2013517 (1977)","journal-title":"SIAM J. on Computing"}],"container-title":["Lecture Notes in Computer Science","Discrete and Computational Geometry"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-46515-7_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,21]],"date-time":"2019-03-21T18:58:17Z","timestamp":1553194697000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-46515-7_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540671817","9783540465157"],"references-count":8,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-46515-7_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000]]}}}