{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,8,6]],"date-time":"2022-08-06T04:12:08Z","timestamp":1659759128449},"reference-count":14,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Inf. &amp; Syst."],"published-print":{"date-parts":[[2022,8,1]]},"DOI":"10.1587\/transinf.2021edp7175","type":"journal-article","created":{"date-parts":[[2022,7,31]],"date-time":"2022-07-31T22:19:35Z","timestamp":1659305975000},"page":"1373-1382","source":"Crossref","is-referenced-by-count":0,"title":["A Polynomial-Time Algorithm for Finding a Spanning Tree with Non-Terminal Set &lt;i&gt;V&lt;sub&gt;NT&lt;\/sub&gt;&lt;\/i&gt; on Circular-Arc Graphs"],"prefix":"10.1587","volume":"E105.D","author":[{"given":"Shin-ichi","family":"NAKAYAMA","sequence":"first","affiliation":[{"name":"Department of Science and Technology, Tokushima University"}]},{"given":"Shigeru","family":"MASUYAMA","sequence":"additional","affiliation":[{"name":"Department of Management, School of Management, Tokyo University of Science"}]}],"member":"532","reference":[{"key":"1","doi-asserted-by":"publisher","unstructured":"[1] K.S. Booth and G.S. Lueker, \u201cTesting for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms,\u201d J. Comput. Syst. Sci., vol.13, no.3, pp.335-379, Dec. 1976. 10.1016\/S0022-0000(76)80045-1","DOI":"10.1016\/S0022-0000(76)80045-1"},{"key":"2","doi-asserted-by":"publisher","unstructured":"[2] H.L. Bodlaender, \u201cAchromatic number is NP-complete for cographs and interval graphs,\u201d Inf. Process. Lett., vol.31, no.3, pp.135-138, May 1989. 10.1016\/0020-0190(89)90221-4","DOI":"10.1016\/0020-0190(89)90221-4"},{"key":"3","doi-asserted-by":"publisher","unstructured":"[3] G. Dur\u00e1n, L.N. Grippo, M.D. Safe, \u201cStructural results on circular-arc graphs and circle graphs: a survey and the main open problems,\u201d Discrete Applied Mathematics, vol.164, pp.427-443, Feb. 2014. 10.1016\/j.dam.2012.12.021","DOI":"10.1016\/j.dam.2012.12.021"},{"key":"4","doi-asserted-by":"publisher","unstructured":"[4] 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":"5","doi-asserted-by":"crossref","unstructured":"[5] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, 1980. 10.1016\/C2013-0-10739-8","DOI":"10.1016\/B978-0-12-289260-8.50010-8"},{"key":"6","doi-asserted-by":"publisher","unstructured":"[6] M.R. Garey, D.S. Johnson, G.L. Miller, and C.H. Papadimitriou, \u201cThe complexity of coloring circular arcs and chords,\u201d SIAM J. Algebraic and Discrete Methods, vol.1, no.2, pp.216-227, 1980. 10.1137\/0601025","DOI":"10.1137\/0601025"},{"key":"7","doi-asserted-by":"publisher","unstructured":"[7] U.I. Gupta, D.T. Lee, and J.Y.-T. Leung, \u201cEfficient algorithms for interval graphs and circular-arc graphs,\u201d Networks, vol.12, no.4, pp.459-467, 1982. 10.1002\/net.3230120410","DOI":"10.1002\/net.3230120410"},{"key":"8","doi-asserted-by":"publisher","unstructured":"[8] J.M. Keil, \u201cFinding Hamiltonian circuits in interval graphs,\u201d IPL, vol.20, no.4, pp.201-206, May 1985. 10.1016\/0020-0190(85)90050-X","DOI":"10.1016\/0020-0190(85)90050-X"},{"key":"9","doi-asserted-by":"publisher","unstructured":"[9] N. Korte and R.H. M\u00f6hring, \u201cAn incremental linear-time algorithm for recognizing interval graphs,\u201d SIAM J. Computing, vol.18, no.1, pp.68-81, 1989. 10.1137\/0218005","DOI":"10.1137\/0218005"},{"key":"10","doi-asserted-by":"publisher","unstructured":"[10] S. Nakayama and S. Masuyama, \u201cA linear time algorithm for finding a spanning tree with non-terminal set <i>V<sub>NT<\/sub><\/i> on cographs,\u201d IEICE Trans. Inf. &amp; Syst., vol.E99-D, no.10, pp.2574-2584, Oct. 2016. 10.1587\/transinf.2016EDP7021","DOI":"10.1587\/transinf.2016EDP7021"},{"key":"11","doi-asserted-by":"publisher","unstructured":"[11] S. Nakayama and S. Masuyama, \u201cA linear time algorithm for finding a minimum spanning tree with non-terminal set <i>V<sub>NT<\/sub><\/i> on outerplanar graphs,\u201d IEICE Trans. Inf. &amp; Syst., vol.E100-D, no.3, pp.434-443, March 2017. \/10.1587\/transinf.2016FCP0010","DOI":"10.1587\/transinf.2016FCP0010"},{"key":"12","doi-asserted-by":"publisher","unstructured":"[12] S. Nakayama and S. Masuyama, \u201cA linear-time algorithm for finding a spanning tree with non-terminal set <i>V<sub>NT<\/sub><\/i> on interval graphs,\u201d IEICE Trans. Inf. &amp; Syst. vol.E101-D, no.9, pp.2235-2246, Sept. 2018. 10.1587\/transinf.2018EDP7047","DOI":"10.1587\/transinf.2018EDP7047"},{"key":"13","doi-asserted-by":"publisher","unstructured":"[13] S. Nakayama and S. Masuyama, \u201cA linear time algorithm for finding a minimum spanning tree with non-terminal set <i>V<sub>NT<\/sub><\/i> on series-parallel graphs,\u201d IEICE Trans. Inf. &amp; Syst. vol.E102-D, no.4, pp.826-835, April 2019. 10.1587\/transinf.2018EDP7232","DOI":"10.1587\/transinf.2018EDP7232"},{"key":"14","doi-asserted-by":"publisher","unstructured":"[14] T. Zhang and Y. Yin, \u201cThe minimum spanning tree problem with non-terminal set,\u201d Informat. Process. Lett., vol.112, no.17-18, pp.688-690, Sept. 2012. 10.1016\/j.ipl.2012.06.012","DOI":"10.1016\/j.ipl.2012.06.012"}],"container-title":["IEICE Transactions on Information and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E105.D\/8\/E105.D_2021EDP7175\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,6]],"date-time":"2022-08-06T03:33:52Z","timestamp":1659756832000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E105.D\/8\/E105.D_2021EDP7175\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,1]]},"references-count":14,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2022]]}},"URL":"https:\/\/doi.org\/10.1587\/transinf.2021edp7175","relation":{},"ISSN":["0916-8532","1745-1361"],"issn-type":[{"value":"0916-8532","type":"print"},{"value":"1745-1361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,1]]},"article-number":"2021EDP7175"}}