{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T07:00:49Z","timestamp":1769238049402,"version":"3.49.0"},"publisher-location":"Cham","reference-count":13,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319539249","type":"print"},{"value":"9783319539256","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-53925-6_18","type":"book-chapter","created":{"date-parts":[[2017,2,20]],"date-time":"2017-02-20T01:12:36Z","timestamp":1487553156000},"page":"228-240","source":"Crossref","is-referenced-by-count":8,"title":["Approximation Algorithm for the Distance-3 Independent Set Problem on Cubic 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":[[2017,2,21]]},"reference":[{"key":"18_CR1","doi-asserted-by":"crossref","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":"2","key":"18_CR2","doi-asserted-by":"crossref","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":"18_CR3","doi-asserted-by":"crossref","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":"18_CR4","doi-asserted-by":"crossref","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":"18_CR5","doi-asserted-by":"crossref","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- $$d$$ independent set problems for bipartite and chordal graphs. J. Comb. Optim. 27(1), 88\u201399 (2014)","journal-title":"J. Comb. Optim."},{"key":"18_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1007\/978-3-319-48749-6_20","volume-title":"Combinatorial Optimization and Applications","author":"H Eto","year":"2016","unstructured":"Eto, H., Ito, T., Liu, Z., Miyano, E.: Approximability of the distance independent set problem on regular graphs and planar graphs. In: Chan, T.-H.H., Li, M., Wang, L. (eds.) COCOA 2016. LNCS, vol. 10043, pp. 270\u2013284. Springer, Heidelberg (2016)"},{"key":"18_CR7","doi-asserted-by":"crossref","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":"18_CR8","doi-asserted-by":"crossref","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":"18_CR9","doi-asserted-by":"crossref","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"},{"key":"18_CR10","doi-asserted-by":"crossref","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"F Harary","year":"1969","unstructured":"Harary, F.: Graph Theory. Addison-Wesley, Reading (1969)"},{"key":"18_CR11","doi-asserted-by":"crossref","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. Algorithm 6, 595\u2013604 (2008)","journal-title":"J. Discret. Algorithm"},{"key":"18_CR12","doi-asserted-by":"crossref","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. Comb. Theory Ser. B 28, 284\u2013304 (1980)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"18_CR13","doi-asserted-by":"crossref","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","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-53925-6_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T21:30:37Z","timestamp":1568842237000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-53925-6_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319539249","9783319539256"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-53925-6_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]}}}