{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T15:27:32Z","timestamp":1725809252380},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319126906"},{"type":"electronic","value":"9783319126913"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-12691-3_33","type":"book-chapter","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T16:11:32Z","timestamp":1415981492000},"page":"444-458","source":"Crossref","is-referenced-by-count":5,"title":["On the Width of Ordered Binary Decision Diagrams"],"prefix":"10.1007","author":[{"given":"Beate","family":"Bollig","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,11,13]]},"reference":[{"key":"33_CR1","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2011.11.029","volume":"447","author":"B Bollig","year":"2012","unstructured":"Bollig, B.: On symbolic OBDD-based algorithms for the minimum spanning tree problem. Theor. Comput. Sci. 447, 2\u201312 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"33_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/978-3-662-44465-8_11","volume-title":"Mathematical Foundations of Computer Science 2014","author":"B Bollig","year":"2014","unstructured":"Bollig, B.: On the complexity of some ordering problems. In: Csuhaj-Varj\u00fa, E., Dietzfelbinger, M., \u00c9sik, Z. (eds.) MFCS 2014, Part II. LNCS, vol. 8635, pp. 118\u2013129. Springer, Heidelberg (2014)"},{"key":"33_CR3","doi-asserted-by":"publisher","unstructured":"Bollig, B., Gill\u00e9, M., Pr\u00f6ger, T.: Implicit computation of maximum bipartite matchings by sublinear functional operations. Theor. Comput. Sci. (2014). doi:\n                      10.1016\/j.tcs.2014.07.020","DOI":"10.1016\/j.tcs.2014.07.020"},{"key":"33_CR4","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0020-0190(96)00119-6","volume":"59","author":"B Bollig","year":"1996","unstructured":"Bollig, B., L\u00f6bbing, M., Wegener, I.: On the effect of local changes in the variable ordering of ordered decision diagrams. Inf. Process. Lett. 59, 233\u2013239 (1996)","journal-title":"Inf. Process. Lett."},{"issue":"9","key":"33_CR5","doi-asserted-by":"publisher","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."},{"key":"33_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/978-3-642-20877-5_32","volume-title":"Theory and Applications of Models of Computation","author":"J Brody","year":"2011","unstructured":"Brody, J., Matulef, K., Wu, C.: Lower bounds for testing computability by small width OBDDs. In: Ogihara, M., Tarui, J. (eds.) TAMC 2011. LNCS, vol. 6648, pp. 320\u2013331. Springer, Heidelberg (2011)"},{"issue":"8","key":"33_CR7","doi-asserted-by":"publisher","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."},{"key":"33_CR8","doi-asserted-by":"crossref","unstructured":"Erg\u00fcn, F., Kumar, R., Rubinfeld, R.: On learning bounded-width branching programs. In: Mass, W. (ed.) COLT, pp. 361\u2013368. ACM (1995)","DOI":"10.1145\/225298.225342"},{"key":"33_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/3-540-08860-1_17","volume-title":"Automata, Languages and Programming","author":"F Fortune","year":"1978","unstructured":"Fortune, F., Hopcroft, J., Schmidt, E.M.: The complexity of equivalence and containment for free single variable program schemes. In: Ausiello, G., B\u00f6hm, C. (eds.) ICALP 1978. LNCS, vol. 62, pp. 227\u2013240. Springer, Heidelberg (1978)"},{"key":"33_CR10","unstructured":"Gavril, F.: Some NP-complete problems on graphs. In: 11th Conference on Information Science and Systems, pp. 91\u201395 (1977)"},{"key":"33_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"574","DOI":"10.1007\/978-3-642-15369-3_43","volume-title":"Approximation, Randomization, and Combinatorial Optimization","author":"O Goldreich","year":"2010","unstructured":"Goldreich, O.: On testing computability by small width OBDDs. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX 2010. LNCS, vol. 6302, pp. 574\u2013587. Springer, Heidelberg (2010)"},{"key":"33_CR12","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1023\/A:1008651924240","volume":"10","author":"G Hachtel","year":"1997","unstructured":"Hachtel, G., Somenzi, F.: A symbolic algorithm for maximum flow in \n                      \n                        \n                      \n                      $$0$$\n                    -\n                      \n                        \n                      \n                      $$1$$\n                     networks. Form. Meth. Syst. Des. 10, 207\u2013219 (1997)","journal-title":"Form. Meth. Syst. Des."},{"issue":"5","key":"33_CR13","doi-asserted-by":"publisher","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":"33_CR14","doi-asserted-by":"publisher","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."},{"issue":"4","key":"33_CR15","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s002360050083","volume":"34","author":"P Savick\u00fd","year":"1997","unstructured":"Savick\u00fd, P., Wegener, I.: Efficient algorithms for the transformation between different types of binary decision diagrams. Acta Informatica 34(4), 245\u2013256 (1997)","journal-title":"Acta Informatica"},{"key":"33_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/978-3-540-24618-3_26","volume-title":"SOFSEM 2004: Theory and Practice of Computer Science","author":"D Sawitzki","year":"2004","unstructured":"Sawitzki, D.: Implicit flow maximization by iterative squaring. In: Van Emde Boas, P., Pokorn\u00fd, J., Bielikov\u00e1, M., \u0160tuller, J. (eds.) SOFSEM 2004. LNCS, vol. 2932, pp. 301\u2013313. Springer, Heidelberg (2004)"},{"key":"33_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/978-3-540-30559-0_13","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"D Sawitzki","year":"2004","unstructured":"Sawitzki, D.: A symbolic approach to the all-pairs shortest-paths problem. In: Hromkovi\u010d, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 154\u2013167. Springer, Heidelberg (2004)"},{"key":"33_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1007\/11611257_45","volume-title":"SOFSEM 2006: Theory and Practice of Computer Science","author":"D Sawitzki","year":"2006","unstructured":"Sawitzki, D.: The complexity of problems on implicitly represented inputs. In: Wiedermann, J., Tel, G., Pokorn\u00fd, J., Bielikov\u00e1, M., \u0160tuller, J. (eds.) SOFSEM 2006. LNCS, vol. 3831, pp. 471\u2013482. Springer, Heidelberg (2006)"},{"key":"33_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1007\/11682462_71","volume-title":"LATIN 2006: Theoretical Informatics","author":"D Sawitzki","year":"2006","unstructured":"Sawitzki, D.: Exponential lower bounds on the space complexity of OBDD-based graph algorithms. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol. 3887, pp. 781\u2013792. Springer, Heidelberg (2006)"},{"key":"33_CR20","doi-asserted-by":"publisher","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":"33_CR21","doi-asserted-by":"crossref","unstructured":"Wegener, I.: Branching programs and binary decision diagrams: theory and applications. SIAM, Philadelphia (2000)","DOI":"10.1137\/1.9780898719789"},{"issue":"1","key":"33_CR22","doi-asserted-by":"publisher","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. Discrete Algorithm 4(1), 51\u201371 (2006)","journal-title":"J. Discrete Algorithm"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-12691-3_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T14:33:30Z","timestamp":1559054010000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-12691-3_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319126906","9783319126913"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-12691-3_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}