{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T22:34:34Z","timestamp":1725834874067},"publisher-location":"Cham","reference-count":41,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319252575"},{"type":"electronic","value":"9783319252582"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-319-25258-2_18","type":"book-chapter","created":{"date-parts":[[2015,10,19]],"date-time":"2015-10-19T07:10:18Z","timestamp":1445238618000},"page":"254-269","source":"Crossref","is-referenced-by-count":1,"title":["Randomized OBDD-Based Graph Algorithms"],"prefix":"10.1007","author":[{"given":"Marc","family":"Bury","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,20]]},"reference":[{"issue":"4","key":"18_CR1","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N. Alon","year":"1986","unstructured":"Alon, N., Babai, L., Itai, A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms\u00a07(4), 567\u2013583 (1986)","journal-title":"J. Algorithms"},{"issue":"3","key":"18_CR2","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1002\/rsa.3240030308","volume":"3","author":"N. Alon","year":"1992","unstructured":"Alon, N., Goldreich, O., H\u00e5stad, J., Peralta, R.: Simple construction of almost k-wise independent random variables. Random Struct. Alg.\u00a03(3), 289\u2013304 (1992)","journal-title":"Random Struct. Alg."},{"issue":"1","key":"18_CR3","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1006\/jcss.1997.1545","volume":"58","author":"N. Alon","year":"1999","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. J. Comp. and System Sc.\u00a058(1), 137\u2013147 (1999)","journal-title":"J. Comp. and System Sc."},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Goldberg, A.V., Luby, M., Plotkin, S.A.: Network decomposition and locality in distributed computation. In: FOCS, pp. 364\u2013369 (1989)","DOI":"10.1109\/SFCS.1989.63504"},{"issue":"1","key":"18_CR5","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s10703-006-4341-z","volume":"28","author":"R. Bloem","year":"2006","unstructured":"Bloem, R., Gabow, H.N., Somenzi, F.: An algorithm for strongly connected component analysis in nlogn symbolic steps. Formal Meth. in System Design\u00a028(1), 37\u201356 (2006)","journal-title":"Formal Meth. in System Design"},{"key":"18_CR6","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.\u00a0447, 2\u201312 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"14-16","key":"18_CR7","doi-asserted-by":"publisher","first-page":"584","DOI":"10.1016\/j.ipl.2013.05.002","volume":"113","author":"B. Bollig","year":"2013","unstructured":"Bollig, B., Capelle, M.: Priority functions for the approximation of the metric TSP. Inf. Proc. Letters\u00a0113(14-16), 584\u2013591 (2013)","journal-title":"Inf. Proc. Letters"},{"key":"18_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/978-3-642-29952-0_45","volume-title":"Theory and Applications of Models of Computation","author":"B. Bollig","year":"2012","unstructured":"Bollig, B., Gill\u00e9, M., Pr\u00f6ger, T.: Implicit computation of maximum bipartite matchings by sublinear functional operations. In: Agrawal, M., Cooper, S.B., Li, A. (eds.) TAMC 2012. LNCS, vol.\u00a07287, pp. 473\u2013486. Springer, Heidelberg (2012)"},{"issue":"5","key":"18_CR9","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. Proc. Letters\u00a059(5), 233\u2013239 (1996)","journal-title":"Inf. Proc. Letters"},{"key":"18_CR10","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/j.ic.2014.08.006","volume":"239","author":"B. Bollig","year":"2014","unstructured":"Bollig, B., Pr\u00f6ger, T.: On efficient implicit OBDD-based algorithms for maximal matchings. Inf. Comput.\u00a0239, 29\u201343 (2014)","journal-title":"Inf. Comput."},{"issue":"8","key":"18_CR11","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(8), 677\u2013691 (1986)","journal-title":"IEEE Transactions on Computers"},{"issue":"2","key":"18_CR12","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/0890-5401(92)90017-A","volume":"98","author":"J.R. Burch","year":"1992","unstructured":"Burch, J.R., Clarke, E.M., McMillan, K.L., Dill, D.L., Hwang, L.J.: Symbolic model checking: 1020 states and beyond. Inf. and Comp.\u00a098(2), 142\u2013170 (1992)","journal-title":"Inf. and Comp."},{"issue":"1","key":"18_CR13","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/0885-064X(89)90015-0","volume":"5","author":"B. Chor","year":"1989","unstructured":"Chor, B., Goldreich, O.: On the power of two-point based sampling. J. Complexity\u00a05(1), 96\u2013106 (1989)","journal-title":"J. Complexity"},{"key":"18_CR14","unstructured":"Coudert, O.: Doing two-level logic minimization 100 times faster. In: SODA, pp. 112\u2013121 (1995)"},{"key":"18_CR15","doi-asserted-by":"crossref","unstructured":"Davis, T.A., Hu, Y.: The University of Florida Sparse Matrix Collection. ACM Trans. on Math. Soft.\u00a038(1), 1:1\u20131:25 (2011)","DOI":"10.1145\/2049662.2049663"},{"key":"18_CR16","unstructured":"Gentilini, R., Piazza, C., Policriti, A.: Computing strongly connected components in a linear number of symbolic steps. In: SODA, pp. 573\u2013582 (2003)"},{"issue":"1","key":"18_CR17","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/s00453-007-9079-5","volume":"50","author":"R. Gentilini","year":"2008","unstructured":"Gentilini, R., Piazza, C., Policriti, A.: Symbolic graphs: Linear solutions to connectivity related problems. Algorithmica\u00a050(1), 120\u2013158 (2008)","journal-title":"Algorithmica"},{"key":"18_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1007\/978-3-642-45043-3_25","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M. Gill\u00e9","year":"2013","unstructured":"Gill\u00e9, M.: OBDD-based representation of interval graphs. In: Brandst\u00e4dt, A., Jansen, K., Reischuk, R. (eds.) WG 2013. LNCS, vol.\u00a08165, pp. 286\u2013297. Springer, Heidelberg (2013)"},{"issue":"2\/3","key":"18_CR19","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 algorithms for maximum flow in 0-1 networks. F. Meth. in Sys. Design\u00a010(2\/3), 207\u2013219 (1997)","journal-title":"F. Meth. in Sys. Design"},{"key":"18_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/3-540-56496-9_31","volume-title":"Computer Aided Verification","author":"R. Hojati","year":"1993","unstructured":"Hojati, R., Touati, H., Kurshan, R.P., Brayton, R.K.: Efficient \u03c9-regular language containment. In: Probst, D.K., von Bochmann, G. (eds.) CAV 1992. LNCS, vol.\u00a0663, pp. 396\u2013409. Springer, Heidelberg (1993)"},{"issue":"2","key":"18_CR21","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0020-0190(86)90144-4","volume":"22","author":"A. Israeli","year":"1986","unstructured":"Israeli, A., Itai, A.: A fast and simple randomized parallel algorithm for maximal matching. Inf. Process. Lett.\u00a022(2), 77\u201380 (1986)","journal-title":"Inf. Process. Lett."},{"key":"18_CR22","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0304-3975(88)90166-1","volume":"57","author":"S. Jukna","year":"1988","unstructured":"Jukna, S.: Entropy of contact circuits and lower bounds on their complexity. Theor. Comput. Sci.\u00a057, 113\u2013129 (1988)","journal-title":"Theor. Comput. Sci."},{"issue":"1-3","key":"18_CR23","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/S0304-3975(02)00643-6","volume":"297","author":"V. Kabanets","year":"2003","unstructured":"Kabanets, V.: Almost k-wise independence and hard Boolean functions. Theor. Comput. Sci.\u00a0297(1-3), 281\u2013295 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"8","key":"18_CR24","doi-asserted-by":"publisher","first-page":"959","DOI":"10.1109\/43.298033","volume":"13","author":"Y. Lai","year":"1994","unstructured":"Lai, Y., Pedram, M., Vrudhula, S.B.K.: EVBDD-based algorithms for integer linear programming, spectral transformation, and function decomposition. IEEE Trans. on CAD of Int. Circuits and Systems\u00a013(8), 959\u2013975 (1994)","journal-title":"IEEE Trans. on CAD of Int. Circuits and Systems"},{"issue":"1","key":"18_CR25","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N. Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput.\u00a021(1), 193\u2013201 (1992)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"18_CR26","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing\u00a015(4), 1036\u20131053 (1986)","journal-title":"SIAM Journal on Computing"},{"key":"18_CR27","unstructured":"Masek, W.: A fast algorithm for the string editing problem and decision graph complexity. Master\u2019s thesis, MIT (1976)"},{"issue":"4","key":"18_CR28","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1016\/j.disc.2008.01.022","volume":"309","author":"K. Meer","year":"2009","unstructured":"Meer, K., Rautenbach, D.: On the OBDD size for graphs of bounded tree- and clique-width. Discrete Mathematics\u00a0309(4), 843\u2013851 (2009)","journal-title":"Discrete Mathematics"},{"issue":"5-6","key":"18_CR29","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/s00446-010-0121-5","volume":"23","author":"Y. M\u00e9tivier","year":"2011","unstructured":"M\u00e9tivier, Y., Robson, J.M., Saheb-Djahromi, N., Zemmari, A.: An optimal bit complexity randomized distributed MIS algorithm. Distributed Computing\u00a023(5-6), 331\u2013340 (2011)","journal-title":"Distributed Computing"},{"issue":"4","key":"18_CR30","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"J. Naor","year":"1993","unstructured":"Naor, J., Naor, M.: Small-bias probability spaces: Efficient constructions and applications. SIAM J. Comput.\u00a022(4), 838\u2013856 (1993)","journal-title":"SIAM J. Comput."},{"key":"18_CR31","doi-asserted-by":"crossref","unstructured":"Negruseri, C.S., Pasoi, M.B., Stanley, B., Stein, C., Strat, C.G.: Solving maximum flow problems on real world bipartite graphs. In: ALENEX, pp. 14\u201328 (2009)","DOI":"10.1137\/1.9781611972894.2"},{"issue":"2","key":"18_CR32","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/j.dam.2008.02.012","volume":"157","author":"R. Nunkesser","year":"2009","unstructured":"Nunkesser, R., Woelfel, P.: Representation of graphs by OBDDs. Discrete Applied Mathematics\u00a0157(2), 247\u2013261 (2009)","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"18_CR33","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1002\/rsa.3240060404","volume":"6","author":"P. Savick\u00fd","year":"1995","unstructured":"Savick\u00fd, P.: Improved Boolean formulas for the Ramsey graphs. Random Struct. Algorithms\u00a06(4), 407\u2013416 (1995)","journal-title":"Random Struct. Algorithms"},{"key":"18_CR34","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":"18_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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.\u00a03831, pp. 471\u2013482. Springer, Heidelberg (2006)"},{"key":"18_CR36","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.\u00a03887, pp. 781\u2013792. Springer, Heidelberg (2006)"},{"key":"18_CR37","unstructured":"Sawitzki, D.: Implicit simulation of FNC algorithms. Electronic Colloquium on Computational Complexity (ECCC)\u00a014(028) (2007)"},{"key":"18_CR38","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 Processing Letters\u00a03, 3\u201312 (1993)","journal-title":"Parallel Processing Letters"},{"issue":"11","key":"18_CR39","doi-asserted-by":"publisher","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. on Comp.\u00a043(11), 1262\u20131269 (1994)","journal-title":"IEEE Trans. on Comp."},{"key":"18_CR40","doi-asserted-by":"crossref","unstructured":"Wegener, I.: Branching programs and binary decision diagrams. In: SIAM Monographs on Discrete Mathematics and Applications (2000)","DOI":"10.1137\/1.9780898719789"},{"key":"18_CR41","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. Disc. Alg.\u00a04, 51\u201371 (2006)","journal-title":"J. Disc. Alg."}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-25258-2_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T07:48:50Z","timestamp":1559288930000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-25258-2_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319252575","9783319252582"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-25258-2_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}