{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T04:49:40Z","timestamp":1764305380271,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,10,14]],"date-time":"2015-10-14T00:00:00Z","timestamp":1444780800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft (DE)","doi-asserted-by":"publisher","award":["BO 2755\/1"],"award-info":[{"award-number":["BO 2755\/1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2016,10]]},"DOI":"10.1007\/s00224-015-9657-x","type":"journal-article","created":{"date-parts":[[2015,10,14]],"date-time":"2015-10-14T03:14:57Z","timestamp":1444792497000},"page":"532-559","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["On the Minimization of (Complete) Ordered Binary Decision Diagrams"],"prefix":"10.1007","volume":"59","author":[{"given":"Beate","family":"Bollig","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,10,14]]},"reference":[{"issue":"10","key":"9657_CR1","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1016\/j.ipl.2009.01.005","volume":"109","author":"B Bollig","year":"2009","unstructured":"Bollig, B.: On the size of (generalized) OBDDs for threshold functions. Inf. Process. Lett. 109(10), 499\u2013503 (2009)","journal-title":"Inf. Process. Lett."},{"key":"9657_CR2","doi-asserted-by":"crossref","unstructured":"Bollig, B.: On the complexity of some ordering problems. In: Proc. of MFCS, LNCS 8635, pp. 118\u2013129. Springer (2014)","DOI":"10.1007\/978-3-662-44465-8_11"},{"key":"9657_CR3","doi-asserted-by":"crossref","unstructured":"Bollig, B.: On the width of ordered binary decision diagrams. In: Proc. of COCOA, LNCS 8881, pp. 444\u2013458. Springer (2014)","DOI":"10.1007\/978-3-319-12691-3_33"},{"issue":"2","key":"9657_CR4","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1007\/s00224-009-9217-3","volume":"47","author":"B Bollig","year":"2010","unstructured":"Bollig, B., Range, N., Wegener, I.: Exact OBDD bounds for some fundamental functions. Theory Comput. Syst. 47(2), 593\u2013609 (2010)","journal-title":"Theory Comput. Syst."},{"issue":"9","key":"9657_CR5","doi-asserted-by":"crossref","first-page":"993","DOI":"10.1109\/12.537122","volume":"45","author":"B Bollig","year":"1996","unstructured":"Bollig, B., Wegener, I.: Improving the variable ordering of OBDDs is NP-complete. IEEE Trans. Comput. 45(9), 993\u20131002 (1996)","journal-title":"IEEE Trans. Comput."},{"issue":"3","key":"9657_CR6","doi-asserted-by":"crossref","first-page":"558","DOI":"10.1006\/jcss.2000.1733","volume":"61","author":"B Bollig","year":"2000","unstructured":"Bollig, B., Wegener, I.: Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems. J. Comput. Syst. Sci. 61(3), 558\u2013579 (2000)","journal-title":"J. Comput. Syst. Sci."},{"key":"9657_CR7","doi-asserted-by":"crossref","unstructured":"Brody, J., Matulef, K., Wu, C.: Lower bounds for testing computability by small width OBDDs. In: TAMC, LNCS 6648, pp. 320\u2013331. Springer (2011)","DOI":"10.1007\/978-3-642-20877-5_32"},{"issue":"8","key":"9657_CR8","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1109\/TC.1986.1676819","volume":"35","author":"R Bryant","year":"1986","unstructured":"Bryant, R.: Graph-based algorithms for boolean function manipulation. IEEE Trans. Comput. 35(8), 677\u2013691 (1986)","journal-title":"IEEE Trans. Comput."},{"issue":"3","key":"9657_CR9","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1145\/568522.568523","volume":"34","author":"J D\u00edaz","year":"2002","unstructured":"D\u00edaz, J., Petit, J., Serna, M.J.: A survey of graph layout problems. ACM Comput. Surv. 34(3), 313\u2013356 (2002)","journal-title":"ACM Comput. Surv."},{"key":"9657_CR10","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, 4th Edition, Graduate texts in mathematics, vol. 173. Springer (2012)","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"9657_CR11","doi-asserted-by":"crossref","unstructured":"Erg\u00fcn, F., Kumar, R., Rubinfeld, R.: On learning bounded-width branching programs. In: COLT, pp. 361\u2013368 (1995)","DOI":"10.1145\/225298.225342"},{"key":"9657_CR12","doi-asserted-by":"crossref","unstructured":"Fortune, F., Hopcroft, J., Schmidt, E.: The complexity of equivalence and containment for free single variable program schemes. In: Proc. of ICALP, LNCS 62, pp. 227\u2013240. Springer (1978)","DOI":"10.1007\/3-540-08860-1_17"},{"key":"9657_CR13","unstructured":"Gavril, F.: Some NP-complete problems on graphs. In: 11th Conference on Information Science and Systems, pp. 91\u201395 (1977)"},{"key":"9657_CR14","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: On testing computability by small width OBDDs. In: APPROX-RANDOM, pp. 574\u2013587 (2010)","DOI":"10.1007\/978-3-642-15369-3_43"},{"issue":"5","key":"9657_CR15","doi-asserted-by":"crossref","first-page":"1557","DOI":"10.1137\/S009753970038211X","volume":"31","author":"I Newman","year":"2002","unstructured":"Newman, I.: Testing membership in languages that have small width branching programs. SIAM J. Comput. 31(5), 1557\u20131570 (2002)","journal-title":"SIAM J. Comput."},{"key":"9657_CR16","doi-asserted-by":"crossref","unstructured":"Ochi, H., Ishiura, N., Yajima, S.: Breadth-first manipulation of SBDD of boolean functions for vector processing. In: DAC, pp. 413\u2013416 (1991)","DOI":"10.1145\/127601.127704"},{"key":"9657_CR17","doi-asserted-by":"crossref","unstructured":"Ochi, H., Yasuoka, K., Yajima, S.: Breadth-first manipulation of very large binary-decision diagrams. In: ICCAD, pp. 48\u201355 (1993)","DOI":"10.1109\/ICCAD.1993.580030"},{"key":"9657_CR18","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1016\/j.tcs.2011.11.007","volume":"420","author":"D Ron","year":"2012","unstructured":"Ron, D., Tsur, G.: Testing computability by width-two OBDDs. Theor. Comput. Sci. 420, 64\u201379 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"9657_CR19","doi-asserted-by":"crossref","unstructured":"Sawitzki, D.: The complexity of problems on implicitly represented inputs. In: Proc. of SOFSEM, LNCS 3831, pp. 471\u2013482. Springer (2006)","DOI":"10.1007\/11611257_45"},{"issue":"2","key":"9657_CR20","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1006\/inco.2001.3076","volume":"172","author":"D Sieling","year":"2002","unstructured":"Sieling, D.: The nonapproximability of OBDD minimization. Inf. Comput. 172(2), 103\u2013138 (2002)","journal-title":"Inf. Comput."},{"key":"9657_CR21","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1142\/S0129626493000022","volume":"3","author":"D Sieling","year":"1993","unstructured":"Sieling, D., Wegener, I.: NC-algorithms for operations on binary decision diagrams. Parallel Process. Lett. 3, 3\u201312 (1993)","journal-title":"Parallel Process. Lett."},{"key":"9657_CR22","doi-asserted-by":"crossref","unstructured":"Tani, S., Hamagushi, K., Yajima, S.: The complexity of the optimal variable ordering problems of a shared binary decision diagram. In: Proc. of ISAAC, LNCS 762, pp. 389\u2013396. Springer (1993)","DOI":"10.1007\/3-540-57568-5_270"},{"issue":"11","key":"9657_CR23","doi-asserted-by":"crossref","first-page":"1262","DOI":"10.1109\/12.324559","volume":"43","author":"I Wegener","year":"1994","unstructured":"Wegener, I.: The size of reduced OBDDs and optimal read-once branching programs for almost all boolean functions. IEEE Trans. Comput. 43(11), 1262\u20131269 (1994)","journal-title":"IEEE Trans. Comput."},{"key":"9657_CR24","doi-asserted-by":"crossref","unstructured":"Wegener, I.: Branching programs and binary decision diagrams: theory and applications. SIAM (2000)","DOI":"10.1137\/1.9780898719789"},{"issue":"1","key":"9657_CR25","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/j.jda.2005.01.008","volume":"4","author":"P Woelfel","year":"2006","unstructured":"Woelfel, P.: Symbolic topological sorting with OBDDs. J. Discret. Algoritm. 4(1), 51\u201371 (2006)","journal-title":"J. Discret. Algoritm."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9657-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-015-9657-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9657-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,31]],"date-time":"2019-08-31T10:47:35Z","timestamp":1567248455000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-015-9657-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,14]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,10]]}},"alternative-id":["9657"],"URL":"https:\/\/doi.org\/10.1007\/s00224-015-9657-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2015,10,14]]}}}