{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:31:47Z","timestamp":1725543107793},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540369257"},{"type":"electronic","value":"9783540369264"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11809678_51","type":"book-chapter","created":{"date-parts":[[2006,8,15]],"date-time":"2006-08-15T09:41:33Z","timestamp":1155634893000},"page":"489-496","source":"Crossref","is-referenced-by-count":1,"title":["Finding Small OBDDs for Incompletely Specified Truth Tables Is Hard"],"prefix":"10.1007","author":[{"given":"Jesper Torp","family":"Kristensen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter Bro","family":"Miltersen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"51_CR1","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1137\/S0097539796302531","volume":"27","author":"M. Bellare","year":"1998","unstructured":"Bellare, M., Goldreich, O., MadhuSudan: Free bits, PCPs, and non- approximability\u2014towards tight results. SIAM J. Comput.\u00a027(3), 804\u2013915 (1998)","journal-title":"SIAM J. Comput."},{"key":"51_CR2","volume-title":"Proceedings of the 22nd ACM\/IEEE Design Automation Conference","author":"R.E. Bryant","year":"1985","unstructured":"Bryant, R.E.: Symbolic manipulation of boolean functions using a graphical representation. In: Proceedings of the 22nd ACM\/IEEE Design Automation Conference. IEEE Computer Society Press, Los Alamitos (1985)"},{"issue":"8","key":"51_CR3","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":"1-3","key":"51_CR4","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1016\/S0304-3975(02)00535-2","volume":"299","author":"L. Engebretsen","year":"2003","unstructured":"Engebretsen, L., Holmerin, J.: Towards optimal lower bounds for clique and chromatic number. Theoret. Comput. Sci.\u00a0299(1-3), 537\u2013584 (2003)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"51_CR5","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1006\/jcss.1998.1587","volume":"57","author":"U. Feige","year":"1998","unstructured":"Feige, U., Kilian, J.: Zero knowledge and the chromatic number. J. Comput. System Sci.\u00a057(2), 187\u2013199 (1998)","journal-title":"J. Comput. System Sci."},{"key":"51_CR6","volume-title":"Computers and intractability","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability. W.H. Freeman and Co., San Francisco (1979)"},{"key":"51_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1007\/3-540-61422-2_125","volume-title":"Algorithm Theory - SWAT \u201996","author":"K. Hirata","year":"1996","unstructured":"Hirata, K., Shimozono, S., Shinohara, A.: On the hardness of approximating the minimum consistent OBDD problem. In: Karlsson, R., Lingas, A. (eds.) SWAT 1996. LNCS, vol.\u00a01097, pp. 112\u2013123. Springer, Heidelberg (1996)"},{"key":"51_CR8","doi-asserted-by":"crossref","first-page":"600","DOI":"10.1109\/SFCS.2001.959936","volume-title":"42nd IEEE Symposiumon Foundations of Computer Science","author":"S. Khot","year":"2001","unstructured":"Khot, S.: Improved in approximability results for MaxClique, chromatic number and approximate graph coloring. In: 42nd IEEE Symposiumon Foundations of Computer Science, Las Vegas, NV, pp. 600\u2013609. IEEE Computer Soc., Los Alamitos (2001)"},{"key":"51_CR9","doi-asserted-by":"crossref","unstructured":"Kiefer, J.C., Flajolet, P., Yang, E.-H.: Data compression via binary decision diagrams. In: Proc. of the 2000 IEEE Intern. Symp. Inform. Theory, Sorrento, Italy, June 25\u201330, p. 296 (2000)","DOI":"10.1109\/ISIT.2000.866594"},{"key":"51_CR10","unstructured":"Kristensen, J.T.: Generation and compression of endgame tables in chess with fast random access using OBDDs. Master\u2019s thesis, University of Aarhus, Department of Computer Science (2005)"},{"issue":"1","key":"51_CR11","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1145\/138027.138042","volume":"40","author":"L.P.M.K. Warmuth","year":"1993","unstructured":"Warmuth, L.P.M.K.: The minimum consistent DFA problem cannot be approximated within any polynomial. J. Assoc. Comput. Mach.\u00a040(1), 95\u2013142 (1993)","journal-title":"J. Assoc. Comput. Mach."},{"key":"51_CR12","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1109\/43.543775","volume":"15","author":"M. Sauerhoff","year":"1996","unstructured":"Sauerhoff, M., Wegener, I.: On the complexity of minimizing the OBDD size for in completely specified functions. IEEE Transactions on Computer-Aided Design\u00a015, 435\u20131437 (1996)","journal-title":"IEEE Transactions on Computer-Aided Design"},{"issue":"4","key":"51_CR13","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0020-0190(98)00065-9","volume":"66","author":"S. Shimozono","year":"1998","unstructured":"Shimozono, S., Hirata, K., Shinohara, A.: On the hardness of approximating the minimum consistent a cyclic DFA and decision diagram. Inform. Process. Lett.\u00a066(4), 165\u2013170 (1998)","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"51_CR14","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1137\/0403025","volume":"3","author":"H.-U. Simon","year":"1990","unstructured":"Simon, H.-U.: On approximate solutions for combinatorial optimization problems. SIAM J. Discrete Math.\u00a03(2), 294\u2013310 (1990)","journal-title":"SIAM J. Discrete Math."},{"key":"51_CR15","doi-asserted-by":"crossref","unstructured":"Wegener, I.: Branching programs and binary decision diagrams. SIAM Mono graphs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics (SIAM) (2000)","DOI":"10.1137\/1.9780898719789"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11809678_51.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:13:45Z","timestamp":1605626025000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11809678_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540369257","9783540369264"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/11809678_51","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}