{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T17:25:38Z","timestamp":1725470738725},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540388753"},{"type":"electronic","value":"9783540388760"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11841036_32","type":"book-chapter","created":{"date-parts":[[2006,9,11]],"date-time":"2006-09-11T13:20:54Z","timestamp":1157980854000},"page":"340-351","source":"Crossref","is-referenced-by-count":7,"title":["On the Complexity of the Multiplication Method for Monotone CNF\/DNF Dualization"],"prefix":"10.1007","author":[{"given":"Khaled M.","family":"Elbassioni","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"32_CR1","volume-title":"Computational Learning Theory","author":"M. Anthony","year":"1992","unstructured":"Anthony, M., Biggs, N.: Computational Learning Theory. Cambridge University Press, Cambridge (1992)"},{"key":"32_CR2","unstructured":"Berge, C.: Hypergraphs. North Holland Mathematical Library, vol.\u00a0445 (1989)"},{"key":"32_CR3","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1006\/inco.1995.1157","volume":"123","author":"J.C. Bioch","year":"1995","unstructured":"Bioch, J.C., Ibaraki, T.: Complexity of identification and dualization of positive Boolean functions. Information and Computation\u00a0123, 50\u201363 (1995)","journal-title":"Information and Computation"},{"key":"32_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1007\/978-3-540-24698-5_52","volume-title":"LATIN 2004: Theoretical Informatics","author":"E. Boros","year":"2004","unstructured":"Boros, E., Elbassioni, K., Gurvich, V., Khachiyan, L.: Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol.\u00a02976, pp. 488\u2013498. Springer, Heidelberg (2004)"},{"issue":"5","key":"32_CR5","doi-asserted-by":"publisher","first-page":"1624","DOI":"10.1137\/S0097539701388768","volume":"31","author":"E. Boros","year":"2002","unstructured":"Boros, E., Elbassioni, K., Gurvich, V., Khachiyan, L., Makino, K.: Dual-bounded generating problems: All minimal integer solutions for a monotone system of linear inequalities. SIAM J. Comput.\u00a031(5), 1624\u20131643 (2002)","journal-title":"SIAM J. Comput."},{"key":"32_CR6","unstructured":"Boros, E., Elbassioni, K., Gurvich, V., Khachiyan, L.: Computing Many Maximal Independent Sets for Hypergraphs in Parallel, DIMACS technical report2004-44, Rutgers University, \n                    \n                      http:\/\/dimacs.rutgers.edu\/TechnicalReports\/2004.html"},{"key":"32_CR7","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1080\/10556789808805708","volume":"10","author":"E. Boros","year":"1998","unstructured":"Boros, E., Gurvich, V., Hammer, P.L.: Dual subimplicants of positive Boolean functions. Optimization Methods and Software\u00a010, 147\u2013156 (1998)","journal-title":"Optimization Methods and Software"},{"key":"32_CR8","volume-title":"The combinatorics of network reliability","author":"C.J. Colbourn","year":"1987","unstructured":"Colbourn, C.J.: The combinatorics of network reliability. Oxford University Press, Oxford (1987)"},{"key":"32_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/3-540-19487-8_16","volume-title":"SWAT \u201988","author":"E. Dahlhaus","year":"1988","unstructured":"Dahlhaus, E., Karpinski, M.: A fast parallel algorithm for computing all maximal cliques in a graph and the related problems. In: Karlsson, R., Lingas, A. (eds.) SWAT 1988. LNCS, vol.\u00a0318, pp. 139\u2013144. Springer, Heidelberg (1988)"},{"key":"32_CR10","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1023\/A:1007627028578","volume":"37","author":"C. Domingo","year":"1999","unstructured":"Domingo, C., Mishra, N., Pitt, L.: Efficient read-restricted monotone CNF\/DNF dualization by learning with membership queries. Machine learning\u00a037, 89\u2013110 (1999)","journal-title":"Machine learning"},{"issue":"3","key":"32_CR11","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1006\/jsco.1994.1013","volume":"17","author":"T. Eiter","year":"1994","unstructured":"Eiter, T.: Exact Transversal Hypergraphs and Application to Boolean \u03bc-Functions. J. Symb. Comput.\u00a017(3), 215\u2013225 (1994)","journal-title":"J. Symb. Comput."},{"key":"32_CR12","doi-asserted-by":"publisher","first-page":"1278","DOI":"10.1137\/S0097539793250299","volume":"24","author":"T. Eiter","year":"1995","unstructured":"Eiter, T., Gottlob, G.: Identifying the minimal transversals of a hypergraph and related problems. SIAM J. Comput.\u00a024, 1278\u20131304 (1995)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"32_CR13","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1137\/S009753970240639X","volume":"32","author":"T. Eiter","year":"2003","unstructured":"Eiter, T., Gottlob, G., Makino, K.: New results on monotone dualization and generating hypergraph transversals. SIAM J. Comput.\u00a032(2), 514\u2013537 (2003)","journal-title":"SIAM J. Comput."},{"key":"32_CR14","unstructured":"Elbassioni, K.: On the complexity of monotone Boolean duality testing, DIMACS Technical Report 2006-1, Rutgers University, \n                    \n                      http:\/\/dimacs.rutgers.edu\/TechnicalReports\/2006.html"},{"key":"32_CR15","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1006\/jagm.1996.0062","volume":"21","author":"M.L. Fredman","year":"1996","unstructured":"Fredman, M.L., Khachiyan, L.: On the complexity of dualization of monotone disjunctive normal forms. J. Algorithms\u00a021, 618\u2013628 (1996)","journal-title":"J. Algorithms"},{"key":"32_CR16","doi-asserted-by":"publisher","first-page":"841","DOI":"10.1145\/4221.4223","volume":"32","author":"H. Garcia-Molina","year":"1985","unstructured":"Garcia-Molina, H., Barbara, D.: How to assign votes in a distributed system. Journal of the ACM\u00a032, 841\u2013860 (1985)","journal-title":"Journal of the ACM"},{"key":"32_CR17","doi-asserted-by":"crossref","unstructured":"Gunopulos, D., Khardon, R., Mannila, H., Toivonen, H.: Data mining, hypergraph transversals and machine learning. In: Proc. the 16th ACM-SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS 1997), pp. 12\u201315 (1997)","DOI":"10.1145\/263661.263684"},{"key":"32_CR18","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1109\/71.238300","volume":"4","author":"T. Ibaraki","year":"1993","unstructured":"Ibaraki, T., Kameda, T.: A theory of coteries: Mutual exclusion in distributed systems. IEEE Transactions on Parallel and Distributed Systems\u00a04, 779\u2013794 (1993)","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"32_CR19","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"D.S. Johnson","year":"1988","unstructured":"Johnson, D.S., Yannakakis, M., Papadimitriou, C.H.: On generating all maximal independent sets. Info. Process. Lett.\u00a027, 119\u2013123 (1988)","journal-title":"Info. Process. Lett."},{"key":"32_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/3-540-57568-5_271","volume-title":"Algorithms and Computation","author":"D.J. Kavvadias","year":"1993","unstructured":"Kavvadias, D.J., Papadimitriou, C., Sideri, M.: On Horn envelopes and hypergraph transversals. In: Ng, K.W., Balasubramanian, N.V., Raghavan, P., Chin, F.Y.L. (eds.) ISAAC 1993. LNCS, vol.\u00a0762, pp. 399\u2013405. Springer, Heidelberg (1993)"},{"key":"32_CR21","first-page":"105","volume-title":"Advances in Convex Analysis and Global Optimization, Honoring the memory of K. Carath\u00e9odory","author":"L. Khachiyan","year":"2000","unstructured":"Khachiyan, L.: Transversal hypergraphs and families of polyhedral cones. In: Hadjisavvas, N., Pardalos, P. (eds.) Advances in Convex Analysis and Global Optimization, Honoring the memory of K. Carath\u00e9odory, pp. 105\u2013118. Kluwer Academic Publishers, Dordrecht (2000)"},{"issue":"4","key":"32_CR22","doi-asserted-by":"publisher","first-page":"966","DOI":"10.1137\/S0895480103428338","volume":"19","author":"L. Khachiyan","year":"2005","unstructured":"Khachiyan, L., Boros, E., Elbassioni, K., Gurvich, V., Makino, K.: On the Complexity of Some Enumeration Problems for Matroids. SIAM J. Discrete Math.\u00a019(4), 966\u2013984 (2005)","journal-title":"SIAM J. Discrete Math."},{"key":"32_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"767","DOI":"10.1007\/11533719_78","volume-title":"Computing and Combinatorics","author":"L. Khachiyan","year":"2005","unstructured":"Khachiyan, L., Boros, E., Elbassioni, K., Gurvich, V.: A New Algorithm for the Hypergraph Transversal Problem. In: Wang, L. (ed.) COCOON 2005. LNCS, vol.\u00a03595, pp. 767\u2013776. Springer, Heidelberg (2005)"},{"key":"32_CR24","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1137\/0209042","volume":"9","author":"E. Lawler","year":"1980","unstructured":"Lawler, E., Lenstra, J.K., Rinnooy Kan, A.H.G.: Generating all maximal independent sets: NP-hardness and polynomial-time algorithms. SIAM J. Comput.\u00a09, 558\u2013565 (1980)","journal-title":"SIAM J. Comput."},{"key":"32_CR25","unstructured":"Lov\u00e1sz, L.: Combinatorial optimization: some problems and trends, DIMACS Technical Report 92-53, Rutgers University (1992)"},{"key":"32_CR26","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/0022-0000(86)90015-2","volume":"22","author":"H. Mannila","year":"1986","unstructured":"Mannila, H., R\u00e4ih\u00e4, K.J.: Design by example: An application of Armstrong relations. Journal of Computer and System Science\u00a022, 126\u2013141 (1986)","journal-title":"Journal of Computer and System Science"},{"key":"32_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/3-540-63165-8_160","volume-title":"Automata, Languages and Programming","author":"C. Papadimitriou","year":"1997","unstructured":"Papadimitriou, C.: NP-completeness: A retrospective. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) ICALP 1997. LNCS, vol.\u00a01256, pp. 2\u20136. Springer, Heidelberg (1997)"},{"key":"32_CR28","doi-asserted-by":"crossref","unstructured":"Mishra, N., Pitt, L.: Generating all maximal independent sets of bounded-degree hypergraphs. In: Proceedings of the 10th Annual Conference on Computational Learning Theory (COLT), Nashville, TN, pp. 211\u2013217 (1997)","DOI":"10.1145\/267460.267500"},{"key":"32_CR29","doi-asserted-by":"crossref","DOI":"10.1007\/978-94-009-2099-6","volume-title":"Coherent Structures and Simple Games","author":"K.G. Ramamurthy","year":"1990","unstructured":"Ramamurthy, K.G.: Coherent Structures and Simple Games. Kluwer Academic Publishers, Dordrecht (1990)"},{"key":"32_CR30","unstructured":"Takata, K.: On the sequential method for listing minimal hitting sets. In: Proc. SIAM Workshop on Discrete Mathematics and Data Mining (DM & DM), Arlington, VA, pp. 109\u2013120 (April 2002)"},{"key":"32_CR31","first-page":"29","volume":"75","author":"H. Tamaki","year":"2000","unstructured":"Tamaki, H.: Space-efficient enumeration of minimal transversals of a hypergraph. IPSJ-AL\u00a075, 29\u201336 (2000)","journal-title":"IPSJ-AL"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11841036_32.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:16:53Z","timestamp":1619507813000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11841036_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540388753","9783540388760"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/11841036_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}