{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,7]],"date-time":"2025-08-07T20:25:56Z","timestamp":1754598356664,"version":"3.40.5"},"reference-count":58,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Inf. &amp; Syst."],"published-print":{"date-parts":[[2014]]},"DOI":"10.1587\/transinf.2014edp7184","type":"journal-article","created":{"date-parts":[[2014,11,30]],"date-time":"2014-11-30T23:30:16Z","timestamp":1417390216000},"page":"3101-3109","source":"Crossref","is-referenced-by-count":4,"title":["Dominating Sets and Induced Matchings in Orthogonal Ray Graphs"],"prefix":"10.1587","volume":"E97.D","author":[{"given":"Asahi","family":"TAKAOKA","sequence":"first","affiliation":[{"name":"Department of Communications and Computer Engineering, Tokyo Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Satoshi","family":"TAYU","sequence":"additional","affiliation":[{"name":"Department of Communications and Computer Engineering, Tokyo Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shuichi","family":"UENO","sequence":"additional","affiliation":[{"name":"Department of Communications and Computer Engineering, Tokyo Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"532","reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"[1] A. Abueida, A.H. Busch, and R. Sritharan, \u201cA min-max property of chordal bipartite graphs with applications,\u201d Graphs and Combinatorics, vol.26, pp.301-313, 2010.","DOI":"10.1007\/s00373-010-0922-0"},{"key":"2","doi-asserted-by":"crossref","unstructured":"[2] H. Balakrishnan, C. Barrett, V. Kumar, M. Marathe, and S. Thite, \u201cThe distance-2 matching problem and its relationship to the MAC-layer capacity of ad hoc wireless networks,\u201d IEEE J. Selected Areas Commun., vol.22, pp.1069-1079, 2004.","DOI":"10.1109\/JSAC.2004.830909"},{"key":"3","doi-asserted-by":"crossref","unstructured":"[3] C.L. Barrett, V.S.A. Kumar, M.V. Marathe, S. Thite, and G. Istrate, \u201cStrong edge coloring for channel assignment in wireless radio networks,\u201d Proceedings of the 4th Annual IEEE International Conference on Pervasive Computing and Communications Workshops, pp.106-110, 2006.","DOI":"10.1109\/PERCOMW.2006.129"},{"key":"4","unstructured":"[4] R. Belmonte and M. Vatshelle, \u201cGraph classes with structured neighborhoods and algorithmic applications,\u201d Proceedings of the 37th international conference on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol.6986, pp.47-58, 2011."},{"key":"5","doi-asserted-by":"crossref","unstructured":"[5] R. Belmonte and M. Vatshelle, \u201cGraph classes with structured neighborhoods and algorithmic applications,\u201d Theoretical Computer Science, vol.511, pp.54-65, 2013.","DOI":"10.1016\/j.tcs.2013.01.011"},{"key":"6","doi-asserted-by":"crossref","unstructured":"[6] K.P. Bogart, P.C. Fishburn, G. Isaak, and L. Langley, \u201cProper and unit tolerance graphs,\u201d Discrete Applied Mathematics, vol.60, pp.99-117, 1995.","DOI":"10.1016\/0166-218X(94)00044-E"},{"key":"7","doi-asserted-by":"crossref","unstructured":"[7] V. Bonifaci, P. Korteweg, A. Marchetti-Spaccamela, and L. Stougie, \u201cMinimizing flow time in the wireless gathering problem,\u201d ACM Transactions on Algorithms, vol.7, pp.33: 1-33: 20, 2011.","DOI":"10.1145\/1978782.1978788"},{"key":"8","doi-asserted-by":"crossref","unstructured":"[8] A. Brandst\u00e4dt, E.M. Eschen, and R. Sritharan, \u201cThe induced matching and chain subgraph cover problems for convex bipartite graphs,\u201d Theoretical Computer Science, vol.381, pp.260-265, 2007.","DOI":"10.1016\/j.tcs.2007.04.006"},{"key":"9","doi-asserted-by":"crossref","unstructured":"[9] A. Brandst\u00e4dt and C.T. Ho\u00e0ng, \u201cMaximum induced matchings for chordal graphs in linear time,\u201d Algorithmica, vol.52, pp.440-447, 2008.","DOI":"10.1007\/s00453-007-9045-2"},{"key":"10","doi-asserted-by":"crossref","unstructured":"[10] A. Brandst\u00e4dt, V.B. Le, and J.P. Spinrad, Graph Classes: A Survey, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1999.","DOI":"10.1137\/1.9780898719796"},{"key":"11","doi-asserted-by":"crossref","unstructured":"[11] H. Broersma, T. Kloks, D. Kratsch, and H. M\u00fcller, \u201cIndependent sets in asteroidal triple-free graphs,\u201d SIAM Journal on Discrete Mathematics, vol.12, pp.276-287, 1999.","DOI":"10.1137\/S0895480197326346"},{"key":"12","unstructured":"[12] B.-M. Bui-Xuan, J.A. Telle, and M. Vatshelle, \u201cBoolean-width of graphs,\u201d Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC 2009), Lecture Notes in Computer Science, vol.5917, pp.61-74, 2009."},{"key":"13","unstructured":"[13] B.-M. Bui-Xuan, J.A. Telle, and M. Vatshelle, \u201cBoolean-width of graphs,\u201d Theoretical Computer Science, vol.412, pp.5187-5204, 2011."},{"key":"14","doi-asserted-by":"crossref","unstructured":"[14] B.-M. Bui-Xuan, J.A. Telle, and M. Vatshelle, \u201cFast dynamic programming for locally checkable vertex subset and vertex partitioning problems,\u201d Theoretical Computer Science, vol.511, pp.66-76, 2013.","DOI":"10.1016\/j.tcs.2013.01.009"},{"key":"15","doi-asserted-by":"crossref","unstructured":"[15] K. Cameron, \u201cInduced matchings,\u201d Discrete Applied Mathematics, vol.24, pp.97-102, 1989.","DOI":"10.1016\/0166-218X(92)90275-F"},{"key":"16","doi-asserted-by":"crossref","unstructured":"[16] K. Cameron, \u201cInduced matchings in intersection graphs,\u201d Discrete Mathematics, vol.278, pp.1-9, 2004.","DOI":"10.1016\/j.disc.2003.05.001"},{"key":"17","doi-asserted-by":"crossref","unstructured":"[17] K. Cameron, R. Sritharan, and Y. Tang, \u201cFinding a maximum induced matching in weakly chordal graphs,\u201d Discrete Mathematics, vol.266, pp.133-142, 2003.","DOI":"10.1016\/S0012-365X(02)00803-8"},{"key":"18","doi-asserted-by":"crossref","unstructured":"[18] J.-M. Chang, \u201cInduced matchings in asteroidal triple-free graphs,\u201d Discrete Applied Mathematics, vol.132, pp.67-78, 2003.","DOI":"10.1016\/S0166-218X(03)00390-1"},{"key":"19","doi-asserted-by":"crossref","unstructured":"[19] H.S. Chao, F.-R. Hsu, and R.C.T. Lee, \u201cAn optimal algorithm for finding the minimum cardinality dominating set on permutation graphs,\u201d Discrete Applied Mathematics, vol.102, pp.159-173, 2000.","DOI":"10.1016\/S0166-218X(98)00145-0"},{"key":"20","doi-asserted-by":"crossref","unstructured":"[20] I. Dagan, M.C. Golumbic, and R.Y. Pinter, \u201cTrapezoid graphs and their coloring,\u201d Discrete Applied Mathematics, vol.21, pp.35-46, 1988.","DOI":"10.1016\/0166-218X(88)90032-7"},{"key":"21","doi-asserted-by":"crossref","unstructured":"[21] P. Damaschke, H. M\u00fcller, and D. Kratsch, \u201cDomination in convex and chordal bipartite graphs,\u201d Information Processing Letters, vol.36, pp.231-236, 1990.","DOI":"10.1016\/0020-0190(90)90147-P"},{"key":"22","unstructured":"[22] A. Ershadi, List homomorphisms and bipartite co-circular arc graphs, Master&apos;s thesis, Simon Fraser University, 2012."},{"key":"23","doi-asserted-by":"crossref","unstructured":"[23] T. Feder, P. Hell, and J. Huang, \u201cList homomorphisms and circular arc graphs,\u201d Combinatorica, vol.19, pp.487-505, 1999.","DOI":"10.1007\/s004939970003"},{"key":"24","doi-asserted-by":"crossref","unstructured":"[24] S. Felsner, \u201cTolerance graphs and orders,\u201d Journal of Graph Theory, vol.28, pp.129-140, 1998.","DOI":"10.1002\/(SICI)1097-0118(199807)28:3<129::AID-JGT2>3.0.CO;2-M"},{"key":"25","unstructured":"[25] S. Felsner, G.B. Mertzios, and I. Mustata, \u201cOn the recognition of four-directional orthogonal ray graphs,\u201d Proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, vol.8087, pp.373-384, 2013."},{"key":"26","doi-asserted-by":"crossref","unstructured":"[26] S. Felsner, R. M\u00fcller, and L. Wernisch, \u201cTrapezoid graphs and generalizations, geometry and algorithms,\u201d Discrete Applied Mathematics, vol.74, pp.13-32, 1997.","DOI":"10.1016\/S0166-218X(96)00013-3"},{"key":"27","doi-asserted-by":"crossref","unstructured":"[27] T. Gallai, \u201cTransitiv orientierbare graphen,\u201d Acta Mathematica Academiae Scientiarum Hungarica, vol.18, pp.25-66, 1967.","DOI":"10.1007\/BF02020961"},{"key":"28","doi-asserted-by":"crossref","unstructured":"[28] B. Gamble, W.R. Pulleyblank, B. Reed, and F.B. Shepherd, \u201cRight angle free subsets in the plane,\u201d Graphs and Combinatorics, vol.11, pp.121-129, 1995.","DOI":"10.1007\/BF01929481"},{"key":"29","unstructured":"[29] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theroy of NP-Completeness, W.H. Freeman and Company, 1979."},{"key":"30","doi-asserted-by":"crossref","unstructured":"[30] M.C. Golumbic, Algorithmic graph theory and perfect graphs, in vol.57 of Annals of Discrete Mathematics, 2 ed., Elsevier, 2004.","DOI":"10.1016\/S0167-5060(04)80051-7"},{"key":"31","doi-asserted-by":"crossref","unstructured":"[31] M.C. Golumbic and R. Laskar, \u201cIrredundancy in circular arc graphs,\u201d Discrete Applied Mathematics, vol.44, pp.79-89, 1993.","DOI":"10.1016\/0166-218X(93)90223-B"},{"key":"32","doi-asserted-by":"crossref","unstructured":"[32] M.C. Golumbic and M. Lewenstein, \u201cNew results on induced matchings,\u201d Discrete Applied Mathematics, vol.101, pp.157-165, 2000.","DOI":"10.1016\/S0166-218X(99)00194-8"},{"key":"33","doi-asserted-by":"crossref","unstructured":"[33] P.L. Hammer, U.N. Peled, and X. Sun, \u201cDifference graphs,\u201d Discrete Applied Mathematics, vol.28, pp.35-44, 1990.","DOI":"10.1016\/0166-218X(90)90092-Q"},{"key":"34","doi-asserted-by":"crossref","unstructured":"[34] J. Huang, \u201cRepresentation characterizations of chordal bipartite graphs,\u201d Journal of Combinatorial Theory Series B, vol.96, pp.673-683, 2006.","DOI":"10.1016\/j.jctb.2006.01.001"},{"key":"35","unstructured":"[35] J.M. Keil, \u201cThe dominating set problem in interval bigraphs, abstract,\u201d Proceedings of the 3rd Annual Workshop on Algorithmic Graph Theory, p.1, 2012."},{"key":"36","doi-asserted-by":"crossref","unstructured":"[36] J.M. Keil and P. Belleville, \u201cDominating the complements of bounded tolerance graphs and the complements of trapezoid graphs,\u201d Discrete Applied Mathematics, vol.140, pp.73-89, 2004.","DOI":"10.1016\/j.dam.2003.04.004"},{"key":"37","unstructured":"[37] S. Kijima, Y. Okamoto, and T. Uno, \u201cDominating set counting in graph classes,\u201d Proceedings of the 17th Annual International Computing and Combinatorics Conference, Lecture Notes in Computer Science, vol.6842, pp.13-24, 2011."},{"key":"38","doi-asserted-by":"crossref","unstructured":"[38] C.M. Krishnamurthy and R. Sritharan, \u201cMaximum induced matching problem on hhd-free graphs,\u201d Discrete Applied Mathematics, vol.160, pp.224-230, 2012.","DOI":"10.1016\/j.dam.2011.08.027"},{"key":"39","doi-asserted-by":"crossref","unstructured":"[39] T.-H. Ma and J. Spinrad, \u201cOn the 2-chain subgraph cover and related problems,\u201d Journal of Algorithms, vol.17, pp.251-268, 1994.","DOI":"10.1006\/jagm.1994.1034"},{"key":"40","doi-asserted-by":"crossref","unstructured":"[40] M. Mahdian, \u201cOn the computational complexity of strong edge coloring,\u201d Discrete Applied Mathematics, vol.118, pp.239-248, 2002.","DOI":"10.1016\/S0166-218X(01)00237-2"},{"key":"41","doi-asserted-by":"crossref","unstructured":"[41] R.M. McConnell and J. Spinrad, \u201cModular decomposition and transitive orientation,\u201d Discrete Mathematics, vol.201, pp.189-241, 1999.","DOI":"10.1016\/S0012-365X(98)00319-7"},{"key":"42","doi-asserted-by":"crossref","unstructured":"[42] N. Milosavljevic, \u201cOn complexity of wireless gathering problems on unit-disk graphs,\u201d Ad-hoc, Mobile, and Wireless Networks, Lecture Notes in Computer Science, vol.6811, pp.308-321, 2011.","DOI":"10.1007\/978-3-642-22450-8_24"},{"key":"43","doi-asserted-by":"crossref","unstructured":"[43] H. M\u00fcller and A. Brandst\u00e4dt, \u201cThe NP-completeness of Steiner tree and dominating set for chordal bipartite graphs,\u201d Theoretical Computer Science, vol.53, pp.257-265, 1987.","DOI":"10.1016\/0304-3975(87)90067-3"},{"key":"44","unstructured":"[44] I. Mustata, K. Nishikawa, A. Takaoka, S. Tayu, and S. Ueno, On orthogonal ray trees. in preparation."},{"key":"45","unstructured":"[45] I. Mustata, M. Pergel, A. Takaoka, S. Tayu, and S. Ueno, \u201cOn unit grid intersection graphs,\u201d Submitted."},{"key":"46","unstructured":"[46] C.G. Plaxton, \u201cVertex-weighted matching in two-directional orthogonal ray graphs,\u201d Proceedings of the 24th International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, vol.8283, pp.524-534, 2013."},{"key":"47","doi-asserted-by":"crossref","unstructured":"[47] C.J. Rhee, Y.D. Liang, S.K. Dhall, and S. Lakshmivarahan, \u201cAn <i>O<\/i>(<i>N<\/i>+<i>M<\/i>)-time algorithm for finding a minimum-weight dominating set in a permutation graph,\u201d SIAM Journal on Computing, vol.25, pp.404-419, 1996.","DOI":"10.1137\/S0097539794200383"},{"key":"48","unstructured":"[48] A.M.S. Shrestha, Study of orthogonal ray graphs with applications to nano-circuit design, PhD thesis, Department of Communications and Integrated Systems, Tokyo Institute of Technology, 2011."},{"key":"49","doi-asserted-by":"crossref","unstructured":"[49] A.M.S. Shrestha, A. Takaoka, S. Tayu, and S. Ueno, \u201cOn two problems of nano-PLA design,\u201d IEICE Trans. Inf. &amp; Syst., vol.E94-D, no.1, pp.35-41, Jan. 2011.","DOI":"10.1587\/transinf.E94.D.35"},{"key":"50","unstructured":"[50] A.M.S. Shrestha, S. Tayu, and S. Ueno, \u201cOn orthogonal ray graphs,\u201d Discrete Applied Mathematics, vol.158, pp.1650-1659, 2010."},{"key":"51","unstructured":"[51] J.A. Soto, Contributions on secretary problems, independent sets of rectangles and related problems, PhD thesis, Massachusetts Institute of Technology, 2011."},{"key":"52","unstructured":"[52] J.A. Soto and C. Telha, \u201cJump number of two-directional orthogonal ray graphs,\u201d Proceedings of the 15th International Conference on Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, vol.6655, pp.389-403, 2011."},{"key":"53","doi-asserted-by":"crossref","unstructured":"[53] J.P. Spinrad, \u201cEfficient graph representations,\u201d in vol.19 of Fields Institute monographs, American Mathematical Society, 2003.","DOI":"10.1090\/fim\/019"},{"key":"54","doi-asserted-by":"crossref","unstructured":"[54] L.J. Stockmeyer and V.V. Vazirani, \u201cNP-completeness of some generalizations of the maximum matching problem,\u201d Information Processing Letters, vol.15, pp.14-19, 1982.","DOI":"10.1016\/0020-0190(82)90077-1"},{"key":"55","doi-asserted-by":"crossref","unstructured":"[55] W.T. Trotter and J.I. Moore, \u201cCharacterization problems for graphs, partially ordered sets, lattices, and families of sets,\u201d Discrete Mathematics, vol.16, pp.361-381, 1976.","DOI":"10.1016\/S0012-365X(76)80011-8"},{"key":"56","unstructured":"[56] M. Vatshelle, Personal communication, 2013."},{"key":"57","doi-asserted-by":"crossref","unstructured":"[57] J.R. Walter, \u201cRepresentations of chordal graphs as subtrees of a tree,\u201d Journal of Graph Theory, vol.2, pp.265-267, 1978.","DOI":"10.1002\/jgt.3190020311"},{"key":"58","doi-asserted-by":"crossref","unstructured":"[58] M. Yannakakis, \u201cThe complexity of the partial order dimension problem,\u201d SIAM Journal on Algebraic and Discrete Methods, vol.3, pp.351-358, 1982.","DOI":"10.1137\/0603036"}],"container-title":["IEICE Transactions on Information and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E97.D\/12\/E97.D_2014EDP7184\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T21:51:48Z","timestamp":1747173108000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E97.D\/12\/E97.D_2014EDP7184\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"references-count":58,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2014]]}},"URL":"https:\/\/doi.org\/10.1587\/transinf.2014edp7184","relation":{},"ISSN":["0916-8532","1745-1361"],"issn-type":[{"type":"print","value":"0916-8532"},{"type":"electronic","value":"1745-1361"}],"subject":[],"published":{"date-parts":[[2014]]}}}