{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:18:52Z","timestamp":1759637932657},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540327554"},{"type":"electronic","value":"9783540327561"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11682462_71","type":"book-chapter","created":{"date-parts":[[2006,2,17]],"date-time":"2006-02-17T11:50:30Z","timestamp":1140177030000},"page":"781-792","source":"Crossref","is-referenced-by-count":11,"title":["Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms"],"prefix":"10.1007","author":[{"given":"Daniel","family":"Sawitzki","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"71_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1007\/11427186_39","volume-title":"Experimental and Efficient Algorithms","author":"B. Becker","year":"2005","unstructured":"Becker, B., Behle, M., Eisenbrand, F., Wimmer, R.: BDDs in a branch and cut framework. In: Nikoletseas, S.E. (ed.) WEA 2005. LNCS, vol.\u00a03503, pp. 452\u2013463. Springer, Heidelberg (2005)"},{"key":"71_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/11555964_4","volume-title":"Computer Algebra in Scientific Computing","author":"R. Berghammer","year":"2005","unstructured":"Berghammer, R., Neumann, F.: RELVIEW - An OBDD-based computer algebra system for relations. In: Ganzha, V.G., Mayr, E.W., Vorozhtsov, E.V. (eds.) CASC 2005. LNCS, vol.\u00a03718, pp. 40\u201351. Springer, Heidelberg (2005)"},{"key":"71_CR3","first-page":"688","volume-title":"DAC 1985","author":"R.E. Bryant","year":"1985","unstructured":"Bryant, R.E.: Symbolic manipulation of Boolean functions using a graphical representation. In: DAC 1985, pp. 688\u2013694. ACM Press, New York (1985)"},{"key":"71_CR4","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1109\/TC.1986.1676819","volume":"35","author":"R.E. Bryant","year":"1986","unstructured":"Bryant, R.E.: Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers\u00a035, 677\u2013691 (1986)","journal-title":"IEEE Transactions on Computers"},{"key":"71_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"71_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/BFb0028563","volume-title":"STACS 98","author":"J. Feigenbaum","year":"1998","unstructured":"Feigenbaum, J., Kannan, S., Vardi, M.Y., Viswanathan, M.: Complexity of problems on graphs represented as OBDDs. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol.\u00a01373, pp. 216\u2013226. Springer, Heidelberg (1998)"},{"key":"71_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/3-540-60454-5_41","volume-title":"Algorithmic Learning Theory","author":"R. Gavalda","year":"1995","unstructured":"Gavalda, R., Guijarro, D.: Learning Ordered Binary Decision Diagrams. In: Zeugmann, T., Shinohara, T., Jantke, K.P. (eds.) ALT 1995. LNCS, vol.\u00a0997, pp. 228\u2013238. Springer, Heidelberg (1995)"},{"key":"71_CR8","first-page":"573","volume-title":"SODA 2003","author":"R. Gentilini","year":"2003","unstructured":"Gentilini, R., Piazza, C., Policriti, A.: Computing strongly connected components in a linear number of symbolic steps. In: SODA 2003, pp. 573\u2013582. ACM Press, New York (2003)"},{"key":"71_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1007\/978-3-540-24587-2_57","volume-title":"Algorithms and Computation","author":"R. Gentilini","year":"2003","unstructured":"Gentilini, R., Policriti, A.: Biconnectivity on symbolically represented graphs: A linear solution. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol.\u00a02906, pp. 554\u2013564. Springer, Heidelberg (2003)"},{"key":"71_CR10","volume-title":"Logic Synthesis and Verification Algorithms","author":"G.D. Hachtel","year":"1996","unstructured":"Hachtel, G.D., Somenzi, F.: Logic Synthesis and Verification Algorithms. Kluwer Academic Publishers, Boston (1996)"},{"key":"71_CR11","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1023\/A:1008651924240","volume":"10","author":"G.D. Hachtel","year":"1997","unstructured":"Hachtel, G.D., Somenzi, F.: A symbolic algorithm for maximum flow in 0\u20131 networks. Formal Methods in System Design\u00a010, 207\u2013219 (1997)","journal-title":"Formal Methods in System Design"},{"key":"71_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/3-540-46002-0_22","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"H. Jin","year":"2002","unstructured":"Jin, H., Kuehlmann, A., Somenzi, F.: Fine-grain conjunction scheduling for symbolic reachability analysis. In: Katoen, J.-P., Stevens, P. (eds.) TACAS 2002. LNCS, vol.\u00a02280, pp. 312\u2013326. Springer, Heidelberg (2002)"},{"key":"71_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/3-540-40922-X_10","volume-title":"Formal Methods in Computer-Aided Design","author":"K. Ravi","year":"2000","unstructured":"Ravi, K., Bloem, R., Somenzi, F.: A comparative study of symbolic algorithms for the computation of fair cycles. In: Johnson, S.D., Hunt Jr., W.A. (eds.) FMCAD 2000. LNCS, vol.\u00a01954, pp. 143\u2013160. Springer, Heidelberg (2000)"},{"key":"71_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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.\u00a02932, pp. 301\u2013313. Springer, Heidelberg (2004)"},{"key":"71_CR15","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.\u00a03353, pp. 154\u2013167. Springer, Heidelberg (2004)"},{"key":"71_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1007\/978-3-540-30577-4_33","volume-title":"SOFSEM 2005: Theory and Practice of Computer Science","author":"D. Sawitzki","year":"2005","unstructured":"Sawitzki, D.: Lower bounds on the OBDD size of graphs of some popular functions. In: Vojt\u00e1\u0161, P., Bielikov\u00e1, M., Charron-Bost, B., S\u00fdkora, O. (eds.) SOFSEM 2005. LNCS, vol.\u00a03381, pp. 298\u2013309. Springer, Heidelberg (2005)"},{"key":"71_CR17","doi-asserted-by":"crossref","unstructured":"Sawitzki, D.: The complexity of problems on implicitly represented inputs. In: To appear in SOFSEM 2006 (2006)","DOI":"10.1007\/11611257_45"},{"key":"71_CR18","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719789","volume-title":"Branching Programs and Binary Decision Diagrams","author":"I. Wegener","year":"2000","unstructured":"Wegener, I.: Branching Programs and Binary Decision Diagrams. SIAM, Philadelphia (2000)"},{"key":"71_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/3-540-44693-1_49","volume-title":"STACS 2001","author":"P. Woelfel","year":"2001","unstructured":"Woelfel, P.: New bounds on the OBDD-size of integer multiplication via universal hashing. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol.\u00a02010, pp. 563\u2013574. Springer, Heidelberg (2001)"},{"key":"71_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1007\/978-3-540-45138-9_61","volume-title":"Mathematical Foundations of Computer Science 2003","author":"P. Woelfel","year":"2003","unstructured":"Woelfel, P.: Symbolic topological sorting with oBDDs. In: Rovan, B., Vojt\u00e1\u0161, P. (eds.) MFCS 2003. LNCS, vol.\u00a02747, pp. 671\u2013680. Springer, Heidelberg (2003)"},{"key":"71_CR21","first-page":"37","volume-title":"ICCAD 1999","author":"A. Xie","year":"1999","unstructured":"Xie, A., Beerel, P.A.: Implicit enumeration of strongly connected components. In: ICCAD 1999, pp. 37\u201340. ACM Press, New York (1999)"}],"container-title":["Lecture Notes in Computer Science","LATIN 2006: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11682462_71","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,12]],"date-time":"2019-03-12T07:31:05Z","timestamp":1552375865000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11682462_71"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540327554","9783540327561"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/11682462_71","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}