{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T23:56:12Z","timestamp":1772927772544,"version":"3.50.1"},"reference-count":15,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Inf. &amp; Syst."],"published-print":{"date-parts":[[2026,3,1]]},"DOI":"10.1587\/transinf.2025fcl0001","type":"journal-article","created":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T22:08:04Z","timestamp":1756073284000},"page":"399-403","source":"Crossref","is-referenced-by-count":0,"title":["An Efficient Algorithm for the Detour Hinge Vertex Problem on Trapezoid Graphs"],"prefix":"10.1587","volume":"E109.D","author":[{"given":"Tomonari","family":"IZUMI","sequence":"first","affiliation":[{"name":"Advanced Course of Electronic and Information Systems Engineering, National Institute of Technology, Kushiro College"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yoko","family":"NAKAJIMA","sequence":"additional","affiliation":[{"name":"Department of Creative Engineering, National Institute of Technology, Kushiro College"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomoyosi","family":"AKIBA","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Toyohashi University of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takashi","family":"YUKAWA","sequence":"additional","affiliation":[{"name":"Department of Information &amp; Management Systems Engineering, Nagaoka University of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hirotoshi","family":"HONMA","sequence":"additional","affiliation":[{"name":"Department of Creative Engineering, National Institute of Technology, Kushiro College"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"532","reference":[{"key":"1","doi-asserted-by":"publisher","unstructured":"[1] J.-M. Chang, C.-C. Hsu, Y.-L. Wang, and T.-Y. Ho, \u201cFinding the set of all hinge vertices for strongly chordal graphs in linear time,\u201d Inf. Sci., vol.99, no.3-4, pp.173-182, 1997. 10.1016\/s0020-0255(96)00272-1","DOI":"10.1016\/S0020-0255(96)00272-1"},{"key":"2","doi-asserted-by":"publisher","unstructured":"[2] H. Honma, Y. Nakajima, Y. Igarashi, and S. Masuyama, \u201cAlgorithm for finding maximum detour hinge vertices of interval graphs,\u201d IEICE Trans. Fundamentals, vol.E97-A, no.6, pp.1365-1369, June 2014. 10.1587\/transfun.e97.a.1365","DOI":"10.1587\/transfun.E97.A.1365"},{"key":"3","doi-asserted-by":"publisher","unstructured":"[3] A. Ili\u0107, \u201cEfficient algorithm for the vertex connectivity of trapezoid graphs,\u201d Inf. Process. Lett., vol.113, no.10-11, pp.398-404, 2013. 10.1016\/j.ipl.2013.02.012","DOI":"10.1016\/j.ipl.2013.02.012"},{"key":"4","doi-asserted-by":"publisher","unstructured":"[4] C. Crespelle and P. Gambette, \u201cUnrestricted and complete breadth-first search of trapezoid graphs in <i>O<\/i>(<i>n<\/i>) time,\u201d Inf. Process. Lett., vol.110, no.12-13, pp.497-502, 2010. 10.1016\/j.ipl.2010.03.015","DOI":"10.1016\/j.ipl.2010.03.015"},{"key":"5","doi-asserted-by":"publisher","unstructured":"[5] G.B. Mertzios and D.G. Corneil, \u201cVertex splitting and the recognition of trapezoid graphs,\u201d Discrete Applied Mathematics, vol.159, no.11, pp.1131-1147, 2011. 10.1016\/j.dam.2011.03.023","DOI":"10.1016\/j.dam.2011.03.023"},{"key":"6","doi-asserted-by":"crossref","unstructured":"[6] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Second Edition, Annals of Discrete Mathematics, vol.57, Elsevier, 2004.","DOI":"10.1016\/S0167-5060(04)80051-7"},{"key":"7","doi-asserted-by":"publisher","unstructured":"[7] T.-Y. Ho, Y.-L. Wang, and M.-T. Juan, \u201cA linear time algorithm for finding all hinge vertices of a permutation graph,\u201d Inf. Process. Lett., vol.59, no.2, pp.103-107, 1996. 10.1016\/0020-0190(96)00092-0","DOI":"10.1016\/0020-0190(96)00092-0"},{"key":"8","unstructured":"[8] F.R. Hsu, M.-K. Shan, H.S. Chao, and R.C.T. Lee, \u201cSome optimal parallel algorithms on interval and circular-arc graphs,\u201d J. Inf. Sci. Eng., vol.21, no.3, pp.627-642, 2005."},{"key":"9","unstructured":"[9] H. Honma and S. Masuyama, \u201cA parallel algorithm for finding all hinge vertices of a trapezoid graph,\u201d IEICE Trans. Fundamentals, vol.E85-A, no.5, pp.1031-1040, May 2002."},{"key":"10","doi-asserted-by":"publisher","unstructured":"[10] D. Bera, M. Pal, and T.K. Pal, \u201cAn efficient algorithm for finding all hinge vertices on trapezoid graphs,\u201d Theory of Computing Systems, vol.36, no.1, pp.17-27, 2003. 10.1007\/s00224-002-1004-3","DOI":"10.1007\/s00224-002-1004-3"},{"key":"11","doi-asserted-by":"publisher","unstructured":"[11] H. Honma, Y. Nakajima, Y. Igarashi, and S. Masuyama, \u201cAlgorithm for identifying the maximum detour hinge vertices of a permutation graph,\u201d IEICE Trans. Fundamentals, vol.E98-A, no.6, pp.1161-1167, June 2015. 10.1587\/transfun.e98.a.1161","DOI":"10.1587\/transfun.E98.A.1161"},{"key":"12","doi-asserted-by":"publisher","unstructured":"[12] H. Honma, Y. Nakajima, and S. Masuyama, \u201cAn algorithm for hinge vertex problem on circular trapezoid graphs,\u201d Journal of Information Processing, vol.25, pp.945-948, 2017. 10.2197\/ipsjjip.25.945","DOI":"10.2197\/ipsjjip.25.945"},{"key":"13","doi-asserted-by":"publisher","unstructured":"[13] H. Honma, Y. Nakajima, and S. Masuyama, \u201cAn algorithm for the influential hinge vertex problem on interval graphs,\u201d Journal of Information Processing, vol.28, no.12, pp.1047-1051, 2020. 10.2197\/ipsjjip.28.1047","DOI":"10.2197\/ipsjjip.28.1047"},{"key":"14","unstructured":"[14] Y. Nakajima, S. Nameki, T. Izumi, and H. Honma, \u201cAlgorithm for solving the detour hinge vertex problem on circular-arc graphs,\u201d J. Engineering and Digital Technology, vol.11, no.1, pp.1-7, 2023."},{"key":"15","doi-asserted-by":"publisher","unstructured":"[15] S. Mondal, M. Pal, and T.K. Pal, \u201cAn optimal algorithm for solving all-pairs shortest paths on trapezoid graphs,\u201d Int. J. Comput. Eng. Sci., vol.3, no.2, pp.103-116, 2002. 10.1142\/S1465876302000575","DOI":"10.1142\/S1465876302000575"}],"container-title":["IEICE Transactions on Information and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E109.D\/3\/E109.D_2025FCL0001\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T04:10:47Z","timestamp":1772856647000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E109.D\/3\/E109.D_2025FCL0001\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,1]]},"references-count":15,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026]]}},"URL":"https:\/\/doi.org\/10.1587\/transinf.2025fcl0001","relation":{},"ISSN":["0916-8532","1745-1361"],"issn-type":[{"value":"0916-8532","type":"print"},{"value":"1745-1361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,1]]},"article-number":"2025FCL0001"}}