{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,4]],"date-time":"2026-07-04T07:32:47Z","timestamp":1783150367169,"version":"3.54.6"},"reference-count":22,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Fundamentals"],"published-print":{"date-parts":[[2022,9,1]]},"DOI":"10.1587\/transfun.2021dmp0017","type":"journal-article","created":{"date-parts":[[2022,3,8]],"date-time":"2022-03-08T22:10:03Z","timestamp":1646777403000},"page":"1211-1222","source":"Crossref","is-referenced-by-count":1,"title":["Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs"],"prefix":"10.1587","volume":"E105.A","author":[{"given":"Hiroshi","family":"ETO","sequence":"first","affiliation":[{"name":"Tohoku University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Takehiro","family":"ITO","sequence":"additional","affiliation":[{"name":"Tohoku University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhilong","family":"LIU","sequence":"additional","affiliation":[{"name":"Kyushu Insitute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eiji","family":"MIYANO","sequence":"additional","affiliation":[{"name":"Kyushu Insitute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"532","reference":[{"key":"1","doi-asserted-by":"publisher","unstructured":"[1] G. Agnarsson, P. Damaschke, and M.H. Halld\u00f3rsson, \u201cPowers of geometric intersection graphs and dispersion algorithmsm,\u201d Discrete Appl. Math., vol.132, pp.3-16, 2003. 10.1016\/s0166-218x(03)00386-x","DOI":"10.1016\/S0166-218X(03)00386-X"},{"key":"2","doi-asserted-by":"publisher","unstructured":"[2] B.S. Baker, \u201cApproximation algorithms for NP-complete problems on planar graphs,\u201d J. ACM, vol.41, no.1, pp.153-180, 1994. 10.1145\/174644.174650","DOI":"10.1145\/174644.174650"},{"key":"3","doi-asserted-by":"publisher","unstructured":"[3] P. Berman and T. Fujito, \u201cOn approximation properties of the independent set problem for low degree graphs,\u201d Theor. Comput. Syst., vol.32, no.2, pp.115-132, 1999. 10.1007\/s002240000113","DOI":"10.1007\/s002240000113"},{"key":"4","doi-asserted-by":"publisher","unstructured":"[4] A. Brandst\u00e4dt and V. Giakoumakis, \u201cMaximum weight independent sets in hole- and co-chair-free graphs,\u201d Inform. Process. Lett., vol.112, no.3, pp.67-71, 2012. 10.1016\/j.ipl.2011.09.015","DOI":"10.1016\/j.ipl.2011.09.015"},{"key":"5","doi-asserted-by":"publisher","unstructured":"[5] R.L. Brooks, \u201cOn colouring the nodes of a network,\u201d Proc. Cambridge Philosophical Society, Math. Phys. Sci., vol.37, no.2, pp.194-197, 1941. 10.1017\/s030500410002168x","DOI":"10.1017\/S030500410002168X"},{"key":"6","doi-asserted-by":"publisher","unstructured":"[6] M. Chleb\u00edk and J. Chleb\u00edkov\u00e1, \u201cComplexity of approximating bounded variants of optimization problems,\u201d Theor. Comput. Sci., vol.354, no.3, pp.320-338, 2006. 10.1016\/j.tcs.2005.11.029","DOI":"10.1016\/j.tcs.2005.11.029"},{"key":"7","doi-asserted-by":"publisher","unstructured":"[7] B. Courcelle, \u201cThe monadic second-order logic of graphs. I. Recognizable sets of finite graphs,\u201d Inf. Comput., vol.85, no.1, pp.12-75, 1990. 10.1016\/0890-5401(90)90043-h","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"8","doi-asserted-by":"publisher","unstructured":"[8] H. Eto, F. Guo, and E. Miyano, \u201cDistance-<i>d<\/i> independent set problems for bipartite and chordal graphs,\u201d J. Comb. Optim., vol.27, no.1, pp.88-99, 2014. 10.1007\/s10878-012-9594-4","DOI":"10.1007\/s10878-012-9594-4"},{"key":"9","doi-asserted-by":"crossref","unstructured":"[9] H. Eto, T. Ito, Z. Liu, and E. Miyano, \u201cApproximability of the distance independent set problem on regular graphs and planar graphs,\u201d COCOA 2016, T.-H.H. Chan, M. Li, and L. Wang, eds., LNCS, vol.10043, pp.270-284, Springer, Heidelberg, 2016. 10.1007\/978-3-319-48749-6_20","DOI":"10.1007\/978-3-319-48749-6_20"},{"key":"10","doi-asserted-by":"crossref","unstructured":"[10] M.R. Garey, D.S. Johnson, and L. Stockmeyer, \u201cSome simplified <i>NP<\/i>-complete graph problems,\u201d Theor. Comput. Sci., vol.1, no.3, pp.237-267, 1976. 10.1016\/0304-3975(76)90059-1","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"11","doi-asserted-by":"crossref","unstructured":"[11] F. Gavril, \u201cAlgorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of chordal graph,\u201d SIAM J. Comput., vol.1, no.2, pp.180-187, 1972. 10.1137\/0201013","DOI":"10.1137\/0201013"},{"key":"12","doi-asserted-by":"publisher","unstructured":"[12] F. Gavril, \u201cAlgorithms on circular-arc graphs,\u201d Networks, vol.4, no.4, pp.357-369, 1974. 10.1002\/net.3230040407","DOI":"10.1002\/net.3230040407"},{"key":"13","doi-asserted-by":"publisher","unstructured":"[13] M.C. Golumbic, \u201cThe complexity of comparability graph recognition and coloring,\u201d Computing, vol.18, pp.199-208, 1977. 10.1007\/bf02253207","DOI":"10.1007\/BF02253207"},{"key":"14","doi-asserted-by":"publisher","unstructured":"[14] M.M. Halld\u00f3rsson and J. Radhakrishnan, \u201cGreed is good: Approximating independent sets in sparse and bounded-degree graphs,\u201d Algorithmica, vol.18, no.1, pp.145-163, 1997. 10.1007\/bf02523693","DOI":"10.1007\/BF02523693"},{"key":"15","doi-asserted-by":"crossref","unstructured":"[15] M.M. Halld\u00f3rsson and J. Radhakrishnan, \u201cImproved approximations of independent sets in bounded-degree graphs,\u201d SWAT&apos;94, LNCS, vol.824, pp.195-206, 1994. 10.1007\/3-540-58218-5_18","DOI":"10.1007\/3-540-58218-5_18"},{"key":"16","doi-asserted-by":"crossref","unstructured":"[16] F. Harary, Graph Theory, Addison-Wesley, 1969.","DOI":"10.21236\/AD0705364"},{"key":"17","doi-asserted-by":"publisher","unstructured":"[17] M. Knor, \u201cSmallest regular graphs of given degree and diameter,\u201d Discussiones Mathematicae Graph Theory, vol.34, pp.187-191, 2014. 10.7151\/dmgt.1702","DOI":"10.7151\/dmgt.1702"},{"key":"18","doi-asserted-by":"publisher","unstructured":"[18] V.V. Lozin and M. Milani\u010d, \u201cA polynomial algorithm to find an independent set of maximum weight in a fork-free graph,\u201d J. Discrete Algorithms, vol.6, no.4, pp.595-604, 2008. 10.1016\/j.jda.2008.04.001","DOI":"10.1016\/j.jda.2008.04.001"},{"key":"19","doi-asserted-by":"publisher","unstructured":"[19] G.J. Minty, \u201cOn maximal independent sets of vertices in claw-free graphs,\u201d J. Combin. Theory Ser. B, vol.28, no.3, pp.284-304, 1980. 10.1016\/0095-8956(80)90074-x","DOI":"10.1016\/0095-8956(80)90074-X"},{"key":"20","doi-asserted-by":"publisher","unstructured":"[20] O.J. Murphy, \u201cComputing independent sets in graphs with large girth,\u201d Discrete Appl. Math., vol.35, no.2, pp.167-170, 1992. 10.1016\/0166-218x(92)90041-8","DOI":"10.1016\/0166-218X(92)90041-8"},{"key":"21","unstructured":"[21] S. Poljak, \u201cA note on stable sets and coloring of graphs,\u201d Comment. Math. Univ. Carolin., vol.15, pp.307-309, 1974."},{"key":"22","doi-asserted-by":"crossref","unstructured":"[22] D. Zuckerman, \u201cLinear degree extractors and the inapproximability of max clique and chromatic number,\u201d Theory of Computing, vol.3, no.1, pp.103-128, 2007.","DOI":"10.1145\/1132516.1132612"}],"container-title":["IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E105.A\/9\/E105.A_2021DMP0017\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,3]],"date-time":"2022-09-03T04:36:05Z","timestamp":1662179765000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E105.A\/9\/E105.A_2021DMP0017\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,1]]},"references-count":22,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2022]]}},"URL":"https:\/\/doi.org\/10.1587\/transfun.2021dmp0017","relation":{},"ISSN":["0916-8508","1745-1337"],"issn-type":[{"value":"0916-8508","type":"print"},{"value":"1745-1337","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,1]]},"article-number":"2021DMP0017"}}