{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T01:13:53Z","timestamp":1768698833967,"version":"3.49.0"},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319487489","type":"print"},{"value":"9783319487496","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-48749-6_20","type":"book-chapter","created":{"date-parts":[[2016,10,30]],"date-time":"2016-10-30T04:16:59Z","timestamp":1477801019000},"page":"270-284","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs"],"prefix":"10.1007","author":[{"given":"Hiroshi","family":"Eto","sequence":"first","affiliation":[]},{"given":"Takehiro","family":"Ito","sequence":"additional","affiliation":[]},{"given":"Zhilong","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Eiji","family":"Miyano","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,10,31]]},"reference":[{"key":"20_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0166-218X(03)00386-X","volume":"132","author":"G Agnarsson","year":"2004","unstructured":"Agnarsson, G., Damaschke, P., Halld\u00f3rsson, M.H.: Powers of geometric intersection graphs and dispersion algorithms. Discret. Appl. Math. 132, 3\u201316 (2004)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"20_CR2","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"BS Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1), 153\u2013180 (1994)","journal-title":"J. ACM"},{"issue":"2","key":"20_CR3","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s002240000113","volume":"32","author":"P Berman","year":"1999","unstructured":"Berman, P., Fujito, T.: On approximation properties of the independent set problem for low degree graphs. Theory Comput. Syst. 32(2), 115\u2013132 (1999)","journal-title":"Theory Comput. Syst."},{"key":"20_CR4","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.ipl.2011.09.015","volume":"112","author":"A Brandst\u00e4dt","year":"2012","unstructured":"Brandst\u00e4dt, A., Giakoumakis, V.: Maximum weight independent sets in hole- and co-chair-free graphs. Inf. Process. Lett. 112, 67\u201371 (2012)","journal-title":"Inf. Process. Lett."},{"key":"20_CR5","unstructured":"Brooks, R.L.: On colouring the nodes of a network. In: Proceedings of Cambridge Philosophical Society, Math. Phys. Sci. 37, 194\u2013197 (1941)"},{"key":"20_CR6","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1016\/j.tcs.2005.11.029","volume":"354","author":"M Chleb\u00edk","year":"2006","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Complexity of approximating bounded variants of optimization problems. Theoret. Comput. Sci. 354, 320\u2013338 (2006)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"20_CR7","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"issue":"1","key":"20_CR8","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/s10878-012-9594-4","volume":"27","author":"H Eto","year":"2014","unstructured":"Eto, H., Guo, F., Miyano, E.: Distance-\n                      \n                        \n                      \n                      $$d$$\n                     independent set problems for bipartite and chordal graphs. J. Comb. Optim. 27(1), 88\u201399 (2014)","journal-title":"J. Comb. Optim."},{"key":"20_CR9","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F Gavril","year":"1972","unstructured":"Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of chordal graph. SIAM J. Comput. 1, 180\u2013187 (1972)","journal-title":"SIAM J. Comput."},{"key":"20_CR10","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1002\/net.3230040407","volume":"4","author":"F Gavril","year":"1974","unstructured":"Gavril, F.: Algorithms on circular-arc graphs. Networks 4, 357\u2013369 (1974)","journal-title":"Networks"},{"key":"20_CR11","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/BF02253207","volume":"18","author":"MC Golumbic","year":"1977","unstructured":"Golumbic, M.C.: The complexity of comparability graph recognition and coloring. Computing 18, 199\u2013208 (1977)","journal-title":"Computing"},{"issue":"1","key":"20_CR12","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF02523693","volume":"18","author":"MM Halld\u00f3rsson","year":"1997","unstructured":"Halld\u00f3rsson, M.M., Radhakrishnan, J.: Greed is good: approximating independent sets in sparse and bounded-degree graphs. Algorithmica 18(1), 145\u2013163 (1997)","journal-title":"Algorithmica"},{"key":"20_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/3-540-58218-5_18","volume-title":"Algorithm Theory \u2014 SWAT \u201994","author":"MM Halld\u00f3rsson","year":"1994","unstructured":"Halld\u00f3rsson, M.M., Radhakrishnan, J.: Improved approximations of independent sets in bounded-degree graphs. In: Schmidt, E.M., Skyum, S. (eds.) SWAT 1994. LNCS, vol. 824, pp. 195\u2013206. Springer, Heidelberg (1994). doi:\n                      10.1007\/3-540-58218-5_18"},{"key":"20_CR14","doi-asserted-by":"crossref","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"F Harary","year":"1969","unstructured":"Harary, F.: Graph Theory. Addison-Wesley, Boston (1969)"},{"key":"20_CR15","doi-asserted-by":"publisher","first-page":"187","DOI":"10.7151\/dmgt.1702","volume":"34","author":"M Knor","year":"2014","unstructured":"Knor, M.: Smallest regular graphs of given degree and diameter. Discuss. Math. Graph Theory 34, 187\u2013191 (2014)","journal-title":"Discuss. Math. Graph Theory"},{"key":"20_CR16","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1016\/j.jda.2008.04.001","volume":"6","author":"VV Lozin","year":"2008","unstructured":"Lozin, V.V., Milani\u010d, M.: A polynomial algorithm to find an independent set of maximum weight in a fork-free graph. J. Discret. Algorithms 6, 595\u2013604 (2008)","journal-title":"J. Discret. Algorithms"},{"key":"20_CR17","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"GJ Minty","year":"1980","unstructured":"Minty, G.J.: On maximal independent sets of vertices in claw-free graphs. J. Combin. Theory Ser. B 28, 284\u2013304 (1980)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1","key":"20_CR18","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(1), 103\u2013128 (2007)","journal-title":"Theory Comput."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-48749-6_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T22:19:05Z","timestamp":1558477145000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-48749-6_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319487489","9783319487496"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-48749-6_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"31 October 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Combinatorial Optimization and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hong Kong","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 December 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 December 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoa2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/conference.cs.cityu.edu.hk\/cocoa2016\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}