{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T15:36:19Z","timestamp":1790868979438,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540642305","type":"print"},{"value":"9783540697053","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0028563","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T07:33:39Z","timestamp":1132644819000},"page":"216-226","source":"Crossref","is-referenced-by-count":21,"title":["Complexity of problems on graphs represented as OBDDs"],"prefix":"10.1007","author":[{"given":"J.","family":"Feigenbaum","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S.","family":"Kannan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M. Y.","family":"Vardi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M.","family":"Viswanathan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,20]]},"reference":[{"key":"21_CR1","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0004-3702(96)00014-8","volume":"86","author":"J. L. Balc\u00e1zar","year":"1996","unstructured":"J. L. Balc\u00e1zar, The Complexity of Searching Implicit Graphs, Aritificial Intelligence, 86 (1996), pp. 171\u2013188.","journal-title":"Aritificial Intelligence"},{"key":"21_CR2","doi-asserted-by":"crossref","unstructured":"J. L. Balc\u00e1zar and A. Lozano, The complexity of graph problems for succinctly represented graphs, in Proc. Graph-Theoretic Concepts in Computer Science, Springer-Verlag, Lecture Notes in Computer Science 411, 1989, pp. 277\u2013285.","DOI":"10.1007\/3-540-52292-1_20"},{"key":"21_CR3","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/978-1-4615-3422-8_30","volume-title":"Computer Science","author":"J. L. Balc\u00e1zar","year":"1992","unstructured":"J. L. Balc\u00e1zar, A. Lozano, and J. Tor\u00e1n, The complexity of Algorithmic Problems on Succinct Instances, Computer Science (R. Baeza-Yates and U. Manber, Eds.), Plenum Press, New York, 1992, pp. 351\u2013377."},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"I. Beer, S. Ben-David, D. Geist, R. Gewirtzman, and M. Yoeli, Methodology and system for practical formal verification of reactive hardware, in Proc. 6th Int'l Conf. on Computer-Aided Verification, Springer-Verlag, Lecture Notes in Computer Science 818, 1994, pp. 182\u2013193.","DOI":"10.1007\/3-540-58179-0_53"},{"key":"21_CR5","doi-asserted-by":"crossref","unstructured":"C. L. Berman, Ordered Binary Decision Diagrams and Circuit Structure, in Proc. IEEE International Conf. on Computer Design, 1989, pp. 392\u2013395.","DOI":"10.1109\/ICCD.1989.63394"},{"key":"21_CR6","series-title":"DIMACS Technical Report 9615","volume-title":"Workshop Summary: Computational and Complexity Issues in Automated Verification","author":"R. Brayton","year":"1996","unstructured":"R. Brayton, A. Emerson, and J. Feigenbaum, Workshop Summary: Computational and Complexity Issues in Automated Verification, DIMACS Technical Report 9615, Rutgers University, Piscataway NJ, June 1996."},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"R. Bryant, Graph-Based Algorithms for Boolean Function Manipulation, IEEE Transactions on Computers, C-35 (1986), pp. 677\u2013691.","DOI":"10.1109\/TC.1986.1676819"},{"key":"21_CR8","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1145\/136035.136043","volume":"24","author":"R. Bryant","year":"1992","unstructured":"R. Bryant, Symbolic Manipulation with Ordered Binary Decision Diagrams, ACM Computing Surveys, 24 (1992), pp. 293\u2013318.","journal-title":"ACM Computing Surveys"},{"key":"21_CR9","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/0890-5401(92)90017-A","volume":"98","author":"J. R. Burch","year":"1992","unstructured":"J. R. Burch, E. M. Clarke, K. L. McMillan, D. L. Dill, and L. J. Hwang, Symbolic model checking: 10 20 states and beyond, Information and Computation, 98 (1992), pp. 142\u2013170.","journal-title":"Information and Computation"},{"key":"21_CR10","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01383968","volume":"6","author":"E. M. Clarke","year":"1995","unstructured":"E. M. Clarke, O. Grumberg, H. Hiraishi, S. Jha, D. E. Long, K. L. McMillan, and L. A. Ness, Verification of the Futurebus+ Cache Coherence Protocol, Formal Methods in System Design, 6 (1995), pp. 217\u2013232.","journal-title":"Formal Methods in System Design"},{"key":"21_CR11","volume-title":"Introduction to Algorithms","author":"T. Cormen","year":"1989","unstructured":"T. Cormen, C. Leiserson, and R. Rivest, Introduction to Algorithms, The M.I.T. Press, Cambridge, MA (1989)."},{"key":"21_CR12","unstructured":"E. A. Emerson and C. L. Lei, Efficient Model Checking in Fragments of the Propositional mu-Calculus, Proc. 1st IEEE Symp. on Logic in Computer Science, 1986, pp. 267\u2013278."},{"key":"21_CR13","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/S0019-9958(83)80004-7","volume":"56","author":"H. Galperin","year":"1983","unstructured":"H. Galperin and A. Wigderson, Succinct Representations of Graphs, Information and Control, 56 (1983), pp. 183\u2013198.","journal-title":"Information and Control"},{"key":"21_CR14","doi-asserted-by":"crossref","unstructured":"O. Kupferman and M. Y. Vardi, Module checking, Proc. 8th Int'l. Conf. on Computer-Aided Verification, Springer-Verlag, Lecture Notes in Computer Science 1102, 1996, pp. 75\u201386.","DOI":"10.1007\/3-540-61474-5_59"},{"key":"21_CR15","volume-title":"Computer-Aided Verification of Coordinating Processes: The Automata-Theoretic Approach","author":"R. Kurshan","year":"1994","unstructured":"R. Kurshan, Computer-Aided Verification of Coordinating Processes: The Automata-Theoretic Approach, Princeton University Press, Princeton NJ, 1994."},{"key":"21_CR16","doi-asserted-by":"crossref","unstructured":"R. Kurshan, The Complexity of Verification, Proc. 26th ACM Symp. on Theory of Computing, Montreal, 1994, pp. 365\u2013371.","DOI":"10.1145\/195058.195194"},{"key":"21_CR17","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-3190-6","volume-title":"Symbolic Model Checking","author":"K. McMillan","year":"1993","unstructured":"K. McMillan, Symbolic Model Checking, Kluwer Academic Publishers, Amsterdam, 1993."},{"key":"21_CR18","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/S0019-9958(86)80009-2","volume":"71","author":"C. Papadimitriou","year":"1986","unstructured":"C. Papadimitriou and M. Yannakakis, A Note on Succinct Representations of Graphs, Information and Control, 71 (1986), pp. 181\u2013185.","journal-title":"Information and Control"},{"key":"21_CR19","doi-asserted-by":"crossref","unstructured":"S. Ponzio, A lower bound for integer multiplication with read-once branching programs, Proc. 27th ACM Symp. on Theory of Computation, Las Vegas, 1995, pp. 130\u2013139.","DOI":"10.1145\/225058.225098"},{"key":"21_CR20","unstructured":"S. Ponzio, Restricted Branching Programs and Hardware Verification, PhD Thesis, MIT, 1995."},{"key":"21_CR21","doi-asserted-by":"crossref","unstructured":"S. Skyum and L. Valiant, A Complexity Theory Based on Boolean Algebra, in Proc. 23rd IEEE Symp. on Foundations of Computer Science, 1982, pp. 244\u2013253.","DOI":"10.1109\/SFCS.1981.3"},{"key":"21_CR22","doi-asserted-by":"crossref","unstructured":"J. Tor\u00e1n, Succinct representations of counting problems, Proc. 6th International Conf. on Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes, Springer-Verlag, Lecture Notes in Computer Science 357, 1988, pp. 415\u2013426.","DOI":"10.1007\/3-540-51083-4_77"},{"key":"21_CR23","unstructured":"H. Veith, Languages Represented by Boolean Formulas, TU Vienna, TR CD 85\/95, 1995."},{"key":"21_CR24","doi-asserted-by":"crossref","unstructured":"H. Veith, Succinct Representation, Leaf Languages, and Projection Reductions, in Proc. 11th IEEE Conf. on Computational Complexity, 1996, pp. 118\u2013126.","DOI":"10.1109\/CCC.1996.507675"}],"container-title":["Lecture Notes in Computer Science","STACS 98"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0028563","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T20:06:34Z","timestamp":1736107594000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0028563"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540642305","9783540697053"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/bfb0028563","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998]]}}}