{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T22:24:25Z","timestamp":1757543065710,"version":"3.28.0"},"reference-count":42,"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":[[2024,9,1]]},"DOI":"10.1587\/transfun.2023dmp0006","type":"journal-article","created":{"date-parts":[[2024,1,14]],"date-time":"2024-01-14T22:13:18Z","timestamp":1705270398000},"page":"1441-1451","source":"Crossref","is-referenced-by-count":2,"title":["International Competition on Graph Counting Algorithms 2023"],"prefix":"10.1587","volume":"E107.A","author":[{"given":"Takeru","family":"INOUE","sequence":"first","affiliation":[{"name":"NTT Communication Science Laboratories, NTT Corporation"},{"name":"NTT Network Innovation Laboratories, NTT Corporation"}]},{"given":"Norihito","family":"YASUDA","sequence":"additional","affiliation":[{"name":"NTT Communication Science Laboratories, NTT Corporation"}]},{"given":"Hidetomo","family":"NABESHIMA","sequence":"additional","affiliation":[{"name":"Graduate Faculty of Interdisciplinary Research, University of Yamanashi"}]},{"given":"Masaaki","family":"NISHINO","sequence":"additional","affiliation":[{"name":"NTT Communication Science Laboratories, NTT Corporation"}]},{"given":"Shuhei","family":"DENZUMI","sequence":"additional","affiliation":[{"name":"NTT Communication Science Laboratories, NTT Corporation"}]},{"given":"Shin-ichi","family":"MINATO","sequence":"additional","affiliation":[{"name":"Graduate School of Informatics, Kyoto University"}]}],"member":"532","reference":[{"key":"1","doi-asserted-by":"publisher","unstructured":"[1] S. Minato, \u201cPower of enumeration \u2014 Recent topics on BDD\/ZDD-based techniques for discrete structure manipulation,\u201d IEICE Trans. Inf. &amp; Syst., vol.E100-D, no.8, pp.1556-1562, Aug. 2017. 10.1587\/transinf.2016loi0002","DOI":"10.1587\/transinf.2016LOI0002"},{"key":"2","doi-asserted-by":"crossref","unstructured":"[2] L. Xing and S.V. Amari, Binary Decision Diagrams and Extensions for System Reliability Analysis, John Wiley &amp; Sons, 2015. 10.1002\/9781119178026","DOI":"10.1002\/9781119178026"},{"key":"3","doi-asserted-by":"publisher","unstructured":"[3] T. Inoue, K. Takano, T. Watanabe, J. Kawahara, R. Yoshinaka, A. Kishimoto, K. Tsuda, S. Minato, and Y. Hayashi, \u201cDistribution loss minimization with guaranteed error bound,\u201d IEEE Trans. Smart Grid, vol.5, no.1, pp.102-111, 2014. 10.1109\/tsg.2013.2288976","DOI":"10.1109\/TSG.2013.2288976"},{"key":"4","doi-asserted-by":"publisher","unstructured":"[4] L. Duenas-Osorio, K. Meel, R. Paredes, and M. Vardi, \u201cCounting-based reliability estimation for power-transmission grids,\u201d Proc. AAAI Conference on Artificial Intelligence, 2017. 10.1609\/aaai.v31i1.11178","DOI":"10.1609\/aaai.v31i1.11178"},{"key":"5","doi-asserted-by":"crossref","unstructured":"[5] K. Nakamura, T. Inoue, M. Nishino, N. Yasuda, and S. Minato, \u201cA fast and exact evaluation algorithm for the expected number of connected nodes: An enhanced network reliability measure,\u201d Proc. IEEE INFOCOM, 2023. 10.1109\/infocom53939.2023.10228897","DOI":"10.1109\/INFOCOM53939.2023.10228897"},{"key":"6","doi-asserted-by":"crossref","unstructured":"[6] J. Kawahara, T. Saitoh, H. Suzuki, and R. Yoshinaka, \u201cSolving the longest oneway-ticket problem and enumerating letter graphs by augmenting the two representative approaches with ZDDs,\u201d Computational Intelligence in Information Systems: Proceedings of the Computational Intelligence in Information Systems Conference (CIIS 2016), pp.294-305, Springer, 2017. 10.1007\/978-3-319-48517-1_26","DOI":"10.1007\/978-3-319-48517-1_26"},{"key":"7","doi-asserted-by":"publisher","unstructured":"[7] A. Takizawa, Y. Miyata, and N. Katoh, \u201cEnumeration of floor plans based on a zero-suppressed binary decision diagram,\u201d International Journal of Architectural Computing, vol.13, no.1, pp.25-44, 2015. 10.1260\/1478-0771.13.1.25","DOI":"10.1260\/1478-0771.13.1.25"},{"key":"8","doi-asserted-by":"crossref","unstructured":"[8] A. Takizawa, Y. Takechi, A. Ohta, N. Katoh, T. Inoue, T. Horiyama, J. Kawahara, and S. Minato, \u201cEnumeration of region partitioning for evacuation planning based on ZDD,\u201d 11th International Symposium on Operations Research and its Applications in Engineering, Technology and Management 2013 (ISORA 2013), pp.1-8, 2013. 10.1049\/cp.2013.2258","DOI":"10.1049\/cp.2013.2258"},{"key":"9","doi-asserted-by":"crossref","unstructured":"[9] T. Maehara, H. Suzuki, and M. Ishihata, \u201cExact computation of influence spread by binary decision diagrams,\u201d Proc. 26th International Conference on World Wide Web, pp.947-956, 2017. 10.1145\/3038912.3052567","DOI":"10.1145\/3038912.3052567"},{"key":"10","doi-asserted-by":"publisher","unstructured":"[10] F. Ishioka, J. Kawahara, M. Mizuta, S. Minato, and K. Kurihara, \u201cEvaluation of hotspot cluster detection using spatial scan statistic based on exact counting,\u201d Jpn. J. Stat. Data. Sci., vol.2, pp.241-262, 2019. 10.1007\/s42081-018-0030-6","DOI":"10.1007\/s42081-018-0030-6"},{"key":"11","doi-asserted-by":"crossref","unstructured":"[11] M. Koibuchi, I. Fujiwara, F. Chaix, and H. Casanova, \u201cTowards ideal hop counts in interconnection networks with arbitrary size,\u201d 2016 Fourth International Symposium on Computing and Networking (CANDAR), pp.188-194, IEEE, 2016. 10.1109\/candar.2016.0042","DOI":"10.1109\/CANDAR.2016.0042"},{"key":"12","doi-asserted-by":"crossref","unstructured":"[12] J. Kawahara, T. Horiyama, K. Hotta, and S.i. Minato, \u201cGenerating all patterns of graph partitions within a disparity bound,\u201d WALCOM: Algorithms and Computation: 11th International Conference and Workshops, WALCOM 2017, Hsinchu, Taiwan, March 2017, Proceedings 11, pp.119-131, Springer, 2017. 10.1007\/978-3-319-53925-6_10","DOI":"10.1007\/978-3-319-53925-6_10"},{"key":"13","doi-asserted-by":"publisher","unstructured":"[13] L.G. Valiant, \u201cThe complexity of enumeration and reliability problems,\u201d SIAM J. Comput., vol.8, no.3, pp.410-421, 1979. 10.1137\/0208032","DOI":"10.1137\/0208032"},{"key":"14","doi-asserted-by":"publisher","unstructured":"[14] R. Tarjan, \u201cEnumeration of the elementary circuits of a directed graph,\u201d SIAM J. Comput., vol.2, no.3, pp.211-216, 1973. 10.1137\/0202017","DOI":"10.1137\/0202017"},{"key":"15","doi-asserted-by":"publisher","unstructured":"[15] R.C. Read and R.E. Tarjan, \u201cBounds on backtrack algorithms for listing cycles, paths, and spanning trees,\u201d Networks, vol.5, no.3, pp.237-252, 1975. 10.1002\/net.1975.5.3.237","DOI":"10.1002\/net.1975.5.3.237"},{"key":"16","doi-asserted-by":"crossref","unstructured":"[16] K. Sekine, H. Imai, and S. Tani, \u201cComputing the Tutte polynomial of a graph of moderate size,\u201d Proc. ISAAC, pp.224-233, 1995. 10.1007\/bfb0015427","DOI":"10.1007\/BFb0015427"},{"key":"17","doi-asserted-by":"crossref","unstructured":"[17] O. Coudert, \u201cSolving graph optimization problems with zbdds,\u201d Proc. European Design and Test Conference. ED &amp; TC 97, pp.224-228, IEEE, 1997. 10.1109\/edtc.1997.582363","DOI":"10.1109\/EDTC.1997.582363"},{"key":"18","doi-asserted-by":"publisher","unstructured":"[18] G. Hardy, C. Lucet, and N. Limnios, \u201cK-terminal network reliability measures with binary decision diagrams,\u201d IEEE Trans. Rel., vol.56, no.3, pp.506-515, 2007. 10.1109\/tr.2007.898572","DOI":"10.1109\/TR.2007.898572"},{"key":"19","unstructured":"[19] D.E. Knuth, The Art of Computer Programming, Addison-Wesley, 2011."},{"key":"20","doi-asserted-by":"publisher","unstructured":"[20] J. Kawahara, T. Inoue, H. Iwashita, and S.i. Minato, \u201cFrontier-based search for enumerating all constrained subgraphs with compressed representation,\u201d IEICE Trans. Fundamentals, vol.E100-A, no.9, pp.1773-1784, Sept. 2017. 10.1587\/transfun.e100.a.1773","DOI":"10.1587\/transfun.E100.A.1773"},{"key":"21","doi-asserted-by":"publisher","unstructured":"[21] T. Inoue, H. Iwashita, J. Kawahara, and S. Minato, \u201cGraphillion: Software library for very large sets of labeled graphs,\u201d Int. J. Softw. Tools Technol. Transf., vol.18, no.1, pp.57-66, 2016. 10.1007\/s10009-014-0352-z","DOI":"10.1007\/s10009-014-0352-z"},{"key":"22","unstructured":"[22] C.P. Gomes, A. Sabharwal, and B. Selman, \u201cModel counting,\u201d Handbook of Satisfiability, pp.993-1014, IOS Press, 2021. 10.3233\/faia201009"},{"key":"23","doi-asserted-by":"publisher","unstructured":"[23] J.K. Fichte, M. Hecher, and F. Hamiti, \u201cThe model counting competition 2020,\u201d ACM J. Exp. Algorithmics, vol.26, pp.1-26, 2021. 10.1145\/3459080","DOI":"10.1145\/3459080"},{"key":"24","doi-asserted-by":"publisher","unstructured":"[24] R.M. Bell and Y. Koren, \u201cLessons from the netflix prize challenge,\u201d ACM SIGKDD Explorations Newsletter, vol.9, no.2, pp.75-79, 2007. 10.1145\/1345448.1345465","DOI":"10.1145\/1345448.1345465"},{"key":"25","doi-asserted-by":"publisher","unstructured":"[25] N. Froleyks, M. Heule, M. Iser, M. J\u00e4rvisalo, and M. Suda, \u201cSAT competition 2020,\u201d Artificial Intelligence, vol.301, p.103572, 2021. 10.1016\/j.artint.2021.103572","DOI":"10.1016\/j.artint.2021.103572"},{"key":"26","doi-asserted-by":"publisher","unstructured":"[26] T. Weber, S. Conchon, D. D\u00e9harbe, M. Heizmann, A. Niemetz, and G. Reger, \u201cThe SMT competition 2015-2018,\u201d J. Satisf. Boolean Model. Comput., vol.11, no.1, pp.221-259, 2019. 10.3233\/sat190123","DOI":"10.3233\/SAT190123"},{"key":"27","unstructured":"[27] C.M. Li and F. Manya, \u201cMaxsat, hard and soft constraints,\u201d Handbook of Satisfiability, pp.903-927, IOS Press, 2021. 10.3233\/faia201007"},{"key":"28","doi-asserted-by":"publisher","unstructured":"[28] P. Marin, M. Narizzano, L. Pulina, A. Tacchella, and E. Giunchiglia, \u201cTwelve years of QBF evaluations: QSAT is PSPACE-hard and it shows,\u201d Fundamenta Informaticae, vol.149, no.1-2, pp.133-158, 2016. 10.3233\/fi-2016-1445","DOI":"10.3233\/FI-2016-1445"},{"key":"29","doi-asserted-by":"crossref","unstructured":"[29] C. Demetrescu, A.V. Goldberg, and D.S. Johnson, The Shortest Path Problem: Ninth DIMACS Implementation Challenge, American Mathematical Soc., 2009. 10.1090\/dimacs\/074","DOI":"10.1090\/dimacs\/074"},{"key":"30","unstructured":"[30] E. Gro\u00dfmann, T. Heuer, C. Schulz, and D. Strash, \u201cThe PACE 2022 parameterized algorithms and computational experiments challenge: Directed feedback vertex set,\u201d 17th International Symposium on Parameterized and Exact Computation (IPEC 2022), Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2022. 10.4230\/LIPIcs.IPEC.2022.26"},{"key":"31","doi-asserted-by":"crossref","unstructured":"[31] G. Punzi, A. Conte, R. Grossi, and A. Marino, \u201cAn efficient algorithm for assessing the number of <i>st<\/i>-paths in large graphs,\u201d Proc. 2023 SIAM International Conference on Data Mining (SDM), pp.289-297, 2023. 10.1137\/1.9781611977653.ch33","DOI":"10.1137\/1.9781611977653.ch33"},{"key":"32","doi-asserted-by":"publisher","unstructured":"[32] E.Q. Martins and M.M. Pascoal, \u201cA new implementation of Yen&apos;s ranking loopless paths algorithm,\u201d Quarterly Journal of the Belgian, French and Italian Operations Research Societies, vol.1, no.2, pp.121-133, 2003. 10.1007\/s10288-002-0010-2","DOI":"10.1007\/s10288-002-0010-2"},{"key":"33","unstructured":"[33] Y. Inoue and S. Minato, \u201cAcceleration of ZDD construction for subgraph enumeration via pathwidth optimization,\u201d Technical Report, TCS-TR-A-16-80, Division of Computer Science, Hokkaido University, 2016."},{"key":"34","doi-asserted-by":"publisher","unstructured":"[34] S. Knight, H.X. Nguyen, N. Falkner, R. Bowden, and M. Roughan, \u201cThe internet topology zoo,\u201d IEEE J. Sel. Areas Commun., vol.29, no.9, pp.1765-1775, 2011. 10.1109\/jsac.2011.111002","DOI":"10.1109\/JSAC.2011.111002"},{"key":"35","doi-asserted-by":"publisher","unstructured":"[35] N. Spring, R. Mahajan, and D. Wetherall, \u201cMeasuring ISP topologies with rocketfuel,\u201d ACM SIGCOMM Comput. Commun. Rev., vol.32, no.4, pp.133-145, 2002. 10.1145\/964725.633039","DOI":"10.1145\/964725.633039"},{"key":"36","doi-asserted-by":"crossref","unstructured":"[36] H. Suzuki, M. Ishihata, and S. Minato, \u201cDesigning survivable networks with zero-suppressed binary decision diagrams,\u201d WALCOM: Algorithms and Computation, M.S. Rahman, K. Sadakane, and W.K. Sung, ed., Cham, pp.273-285, Springer International Publishing, 2020. 10.1007\/978-3-030-39881-1_23","DOI":"10.1007\/978-3-030-39881-1_23"},{"key":"37","doi-asserted-by":"crossref","unstructured":"[37] K. Nakamura, T. Inoue, M. Nishino, and N. Yasuda, \u201cEfficient network reliability evaluation for client-server model,\u201d IEEE GLOBECOM, pp.1-6, 2021. 10.1109\/globecom46510.2021.9685283","DOI":"10.1109\/GLOBECOM46510.2021.9685283"},{"key":"38","doi-asserted-by":"crossref","unstructured":"[38] M. Abseher, N. Musliu, and S. Woltran, \u201cHTD \u2014 A free, open-source framework for (customized) tree decompositions and beyond,\u201d Integration of AI and OR Techniques in Constraint Programming: 14th International Conference, CPAIOR 2017, Padua, Italy, June 2017, Proceedings 14, pp.376-386, Springer, 2017. 10.1007\/978-3-319-59776-8_30","DOI":"10.1007\/978-3-319-59776-8_30"},{"key":"39","doi-asserted-by":"publisher","unstructured":"[39] B.D. McKay and A. Piperno, \u201cPractical graph isomorphism, II,\u201d Journal of symbolic computation, vol.60, pp.94-112, 2014. 10.1016\/j.jsc.2013.09.003","DOI":"10.1016\/j.jsc.2013.09.003"},{"key":"40","doi-asserted-by":"publisher","unstructured":"[40] M. Sakai and H. Nabeshima, \u201cConstruction of an ROBDD for a PB-constraint in band form and related techniques for PB-solvers,\u201d IEICE Trans. Inf. &amp; Syst., vol.E98-D, no.6, pp.1121-1127, June 2015. 10.1587\/transinf.2014fop0007","DOI":"10.1587\/transinf.2014FOP0007"},{"key":"41","doi-asserted-by":"publisher","unstructured":"[41] Y.f. Niu and F.M. Shao, \u201cA practical bounding algorithm for computing two-terminal reliability based on decomposition technique,\u201d Computers &amp; Mathematics with Applications, vol.61, no.8, pp.2241-2246, 2011. 10.1016\/j.camwa.2010.09.033","DOI":"10.1016\/j.camwa.2010.09.033"},{"key":"42","doi-asserted-by":"publisher","unstructured":"[42] N. Tamura, A. Taga, S. Kitagawa, and M. Banbara, \u201cCompiling finite linear CSP into SAT,\u201d Constraints, vol.14, pp.254-272, 2009. 10.1007\/s10601-008-9061-0","DOI":"10.1007\/s10601-008-9061-0"}],"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\/E107.A\/9\/E107.A_2023DMP0006\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,8]],"date-time":"2024-11-08T01:19:39Z","timestamp":1731028779000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E107.A\/9\/E107.A_2023DMP0006\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,1]]},"references-count":42,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2024]]}},"URL":"https:\/\/doi.org\/10.1587\/transfun.2023dmp0006","relation":{},"ISSN":["0916-8508","1745-1337"],"issn-type":[{"type":"print","value":"0916-8508"},{"type":"electronic","value":"1745-1337"}],"subject":[],"published":{"date-parts":[[2024,9,1]]},"article-number":"2023DMP0006"}}