{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T00:02:07Z","timestamp":1778544127307,"version":"3.51.4"},"reference-count":32,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Inf. & Syst."],"published-print":{"date-parts":[[2015]]},"DOI":"10.1587\/transinf.2014edp7281","type":"journal-article","created":{"date-parts":[[2015,4,1]],"date-time":"2015-04-01T15:11:54Z","timestamp":1427901114000},"page":"824-834","source":"Crossref","is-referenced-by-count":2,"title":["OBDD Representation of Intersection Graphs"],"prefix":"10.1587","volume":"E98.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] K.A. Baker, P.C. Fishburn, and F.S. Roberts, \u201cPartial orders of dimension 2,\u201d Networks, vol.2, no.1, pp.11-28, 1972.","DOI":"10.1002\/net.3230020103"},{"key":"2","doi-asserted-by":"crossref","unstructured":"[2] F. Bazzaro and C. Gavoille, \u201cLocalized and compact data-structure for comparability graphs,\u201d Discrete Math., vol.309, no.11, pp.3465-3484, 2009.","DOI":"10.1016\/j.disc.2007.12.091"},{"key":"3","doi-asserted-by":"crossref","unstructured":"[3] S. Benzer, \u201cOn the topology of the genetic fine structure,\u201d Proc. Nat. Acad. Sci. USA, vol.45, no.11, pp.1607-1620, 1959.","DOI":"10.1073\/pnas.45.11.1607"},{"key":"4","doi-asserted-by":"crossref","unstructured":"[4] B. Bollig, \u201cOn symbolic OBDD-based algorithms for the minimum spanning tree problem,\u201d Theor. Comput. Sci., vol.447, pp.2-12, 2012.","DOI":"10.1016\/j.tcs.2011.11.029"},{"key":"5","doi-asserted-by":"crossref","unstructured":"[5] B. Bollig and I. Wegener, \u201cImproving the variable ordering of OBDDs is NP-complete,\u201d IEEE Trans. Comput., vol.45, no.9, pp.993-1002, 1996.","DOI":"10.1109\/12.537122"},{"key":"6","doi-asserted-by":"crossref","unstructured":"[6] 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":"7","doi-asserted-by":"crossref","unstructured":"[7] R.E. Bryant, \u201cGraph-based algorithms for boolean function manipulation,\u201d IEEE Trans. Comput., vol.C-35, no.8, pp.677-691, 1986.","DOI":"10.1109\/TC.1986.1676819"},{"key":"8","doi-asserted-by":"crossref","unstructured":"[8] S. Even, A. Pnueli, and A. Lempel, \u201cPermutation graphs and transitive graphs,\u201d J. ACM, vol.19, no.3, pp.400-410, 1972.","DOI":"10.1145\/321707.321710"},{"key":"9","doi-asserted-by":"crossref","unstructured":"[9] C. Gavoille and C. Paul, \u201cOptimal distance labeling for interval graphs and related graph families,\u201d SIAM J. Discrete Math., vol.22, no.3, pp.1239-1258, 2008.","DOI":"10.1137\/050635006"},{"key":"10","unstructured":"[10] M. Gill\u00e9, \u201cOBDD-based representation of interval graphs,\u201d Proc. 39th International Workshop on Graph-Theoretic Concepts in Computer Science, ser. Lecture Notes in Computer Science, vol.8165, pp.286-297, 2013."},{"key":"11","doi-asserted-by":"crossref","unstructured":"[11] M. Gill\u00e9, \u201cOBDD-based representation of interval graphs,\u201d CoRR, vol.abs\/1305.2772, 2013.","DOI":"10.1007\/978-3-642-45043-3_25"},{"key":"12","doi-asserted-by":"crossref","unstructured":"[12] F. Glover, \u201cMaximum matching in a convex bipartite graph,\u201d Naval Research Logistics Quarterly, vol.14, no.3, pp.313-316, 1967.","DOI":"10.1002\/nav.3800140304"},{"key":"13","doi-asserted-by":"crossref","unstructured":"[13] M.C. Golumbic and C.F. Goss, \u201cPerfect elimination and chordal bipartite graphs,\u201d J. Graph Theory, vol.2, no.2, pp.155-163, 1978.","DOI":"10.1002\/jgt.3190020209"},{"key":"14","doi-asserted-by":"crossref","unstructured":"[14] M.C. Golumbic and A.N. Trenk, Tolerance Graphs, ser. Cambridge studies in advanced mathematics, vol.89, Cambridge University Press, 2004.","DOI":"10.1017\/CBO9780511542985"},{"key":"15","unstructured":"[15] R.L. Graham, D.E. Knuth, and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd ed., Addison-Wesley Longman Publishing, Boston, MA, USA, 1994."},{"key":"16","doi-asserted-by":"crossref","unstructured":"[16] I.B.-A. Hartman, I. Newman, and R. Ziv, \u201cOn grid intersection graphs,\u201d Discrete Math., vol.87, no.1, pp.41-52, 1991.","DOI":"10.1016\/0012-365X(91)90069-E"},{"key":"17","doi-asserted-by":"crossref","unstructured":"[17] S. Kannan, M. Naor, and S. Rudich, \u201cImplicit representation of graphs,\u201d SIAM J. Discrete Math., vol.5, no.4, pp.596-603, 1992.","DOI":"10.1137\/0405049"},{"key":"18","doi-asserted-by":"crossref","unstructured":"[18] H.-T. Liaw and C.-S. Lin, \u201cOn the OBDD-representation of general boolean functions,\u201d IEEE Trans. Comput., vol.41, no.6, pp.661-664, 1992.","DOI":"10.1109\/12.144618"},{"key":"19","doi-asserted-by":"crossref","unstructured":"[19] K. Meer and D. Rautenbach, \u201cOn the OBDD size for graphs of bounded tree- and clique-width,\u201d Discrete Math., vol.309, no.4, pp.843-851, 2009.","DOI":"10.1016\/j.disc.2008.01.022"},{"key":"20","doi-asserted-by":"crossref","unstructured":"[20] R. Nunkesser and P. Woelfel, \u201cRepresentation of graphs by OBDDs,\u201d Discrete Appl. Math., vol.157, no.2, pp.247-261, 2009.","DOI":"10.1016\/j.dam.2008.02.012"},{"key":"21","doi-asserted-by":"crossref","unstructured":"[21] Y. Otachi, Y. Okamoto, and K. Yamazaki, \u201cRelationships between the class of unit grid intersection graphs and other classes of bipartite graphs,\u201d Discrete Appl. Math., vol.155, no.17, pp.2383-2390, 2007.","DOI":"10.1016\/j.dam.2007.07.010"},{"key":"22","doi-asserted-by":"crossref","unstructured":"[22] T. Saitoh, Y. Otachi, K. Yamanaka, and R. Uehara, \u201cRandom generation and enumeration of bipartite permutation graphs,\u201d J. Discrete Algorithms, vol.10, pp.84-97, 2012.","DOI":"10.1016\/j.jda.2011.11.001"},{"key":"23","doi-asserted-by":"crossref","unstructured":"[23] A.M.S. Shrestha, A. Takaoka, S. Tayu, and S. Ueno, \u201cOn two problems of nano-PLA design,\u201d IEICE Trans. Inf. & Syst., vol.E94-D, no.1, pp.35-41, Jan. 2011.","DOI":"10.1587\/transinf.E94.D.35"},{"key":"24","unstructured":"[24] A.M.S. Shrestha, S. Tayu, and S. Ueno, \u201cOn orthogonal ray graphs,\u201d Discrete Appl. Math., vol.158, no.15, pp.1650-1659, 2010."},{"key":"25","doi-asserted-by":"crossref","unstructured":"[25] D. Sieling and I. Wegener, \u201cNC-algorithms for operations on binary decision diagrams,\u201d Parallel Process. Lett., vol.3, no.1, pp.3-12, 1993.","DOI":"10.1142\/S0129626493000022"},{"key":"26","unstructured":"[26] J.A. Soto and C. Telha, \u201cJump number of two-directional orthogonal ray graphs,\u201d Proc. 15th International Conference on Integer Programming and Combinatorial Optimization, ser. Lecture Notes in Computer Science, vol.6655, pp.389-403, 2011."},{"key":"27","doi-asserted-by":"crossref","unstructured":"[27] J.P. Spinrad, \u201cNonredundant 1's in \u0393-free matrices,\u201d SIAM J. Discrete Math., vol.8, no.2, pp.251-257, 1995.","DOI":"10.1137\/S0895480191197210"},{"key":"28","doi-asserted-by":"crossref","unstructured":"[28] J.P. Spinrad, Efficient Graph Representations, ser. Fields Institute Monographs, Providence, vol.19, American Mathematical Society, RI, USA, 2003.","DOI":"10.1090\/fim\/019"},{"key":"29","doi-asserted-by":"crossref","unstructured":"[29] J.P. Spinrad, A. Brandst\u00e4dt, and L. Stewart, \u201cBipartite permutation graphs,\u201d Discrete Appl. Math., vol.18, no.3, pp.279-292, 1987.","DOI":"10.1016\/S0166-218X(87)80003-3"},{"key":"30","doi-asserted-by":"crossref","unstructured":"[30] M. Talamo and P. Vocca, \u201cRepresenting graphs implicitly using almost optimal space,\u201d Discrete Appl. Math., vol.108, no.1-2, pp.193-210, 2001.","DOI":"10.1016\/S0166-218X(00)00225-0"},{"key":"31","doi-asserted-by":"crossref","unstructured":"[31] I. Wegener, Branching Programs and Binary Decision Diagrams: Theory and Applications, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000.","DOI":"10.1137\/1.9780898719789"},{"key":"32","doi-asserted-by":"crossref","unstructured":"[32] C.-W. Yu and G.-H. Chen, \u201cEfficient parallel algorithms for doubly convex-bipartite graphs,\u201d Theor. Comput. Sci., vol.147, no.1-2, pp.249-265, 1995.","DOI":"10.1016\/0304-3975(94)00220-D"}],"container-title":["IEICE Transactions on Information and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E98.D\/4\/E98.D_2014EDP7281\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,22]],"date-time":"2019-08-22T18:44:20Z","timestamp":1566499460000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E98.D\/4\/E98.D_2014EDP7281\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015]]}},"URL":"https:\/\/doi.org\/10.1587\/transinf.2014edp7281","relation":{},"ISSN":["0916-8532","1745-1361"],"issn-type":[{"value":"0916-8532","type":"print"},{"value":"1745-1361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]}}}