{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:57:34Z","timestamp":1725537454857},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642041273"},{"type":"electronic","value":"9783642041280"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-04128-0_13","type":"book-chapter","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T18:16:36Z","timestamp":1252952196000},"page":"143-154","source":"Crossref","is-referenced-by-count":2,"title":["Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs"],"prefix":"10.1007","author":[{"given":"Khaled","family":"Elbassioni","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuhisa","family":"Makino","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Imran","family":"Rauf","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"13_CR1","volume-title":"Computational learning theory: an introduction","author":"M. Anthony","year":"1992","unstructured":"Anthony, M., Biggs, N.: Computational learning theory: an introduction. Cambridge University Press, New York (1992)"},{"key":"13_CR2","volume-title":"Hypergraphs","author":"C. Berge","year":"1989","unstructured":"Berge, C.: Hypergraphs. Elsevier, Amsterdam (1989)"},{"issue":"1","key":"13_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(1), 50\u201363 (1995)","journal-title":"Information and Computation"},{"key":"13_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":"13_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. Computing\u00a031(5), 1624\u20131643 (2002)","journal-title":"SIAM J. Computing"},{"key":"13_CR6","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. Optim. Methods Softw.\u00a010, 147\u2013156 (1998)","journal-title":"Optim. Methods Softw."},{"key":"13_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/3-540-45841-7_10","volume-title":"STACS 2002","author":"E. Boros","year":"2002","unstructured":"Boros, E., Gurvich, V., Khachiyan, L., Makino, K.: On the complexity of generating maximal frequent and minimal infrequent sets. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol.\u00a02285, pp. 133\u2013141. Springer, Heidelberg (2002)"},{"key":"13_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/978-3-642-02927-1_17","volume-title":"ICALP 2009","author":"E. Boros","year":"2009","unstructured":"Boros, E., Makino, K.: A fast and simple parallel algorithm for the monotone duality problem. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. Part I. LNCS, vol.\u00a05555, pp. 183\u2013194. Springer, Heidelberg (2009)"},{"key":"13_CR9","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, NY (1987)"},{"key":"13_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03427-9","volume-title":"Computational Geometry, Algorithms and Applications","author":"M. Berg de","year":"1997","unstructured":"de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry, Algorithms and Applications. Springer, Heidelberg (1997)"},{"issue":"1","key":"13_CR11","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(1), 89\u2013110 (1999)","journal-title":"Machine Learning"},{"issue":"6","key":"13_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. Computing\u00a024(6), 1278\u20131304 (1995)","journal-title":"SIAM J. Computing"},{"issue":"2","key":"13_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. Computing\u00a032(2), 514\u2013537 (2003)","journal-title":"SIAM J. Computing"},{"issue":"11","key":"13_CR14","doi-asserted-by":"publisher","first-page":"2035","DOI":"10.1016\/j.dam.2007.04.017","volume":"156","author":"T. Eiter","year":"2008","unstructured":"Eiter, T., Makino, K., Gottlob, G.: Computational aspects of monotone dualization: A brief survey. Discrete Applied Mathematics\u00a0156(11), 2035\u20132049 (2008)","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"13_CR15","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. Journal of Symbolic Computation\u00a017(3), 215\u2013225 (1994)","journal-title":"Journal of Symbolic Computation"},{"key":"13_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/11841036_32","volume-title":"Algorithms \u2013 ESA 2006","author":"K.M. Elbassioni","year":"2006","unstructured":"Elbassioni, K.M.: On the complexity of the multiplication method for monotone CNF\/DNF dualization. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 340\u2013351. Springer, Heidelberg (2006)"},{"key":"13_CR17","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. Journal of Algorithms\u00a021, 618\u2013628 (1996)","journal-title":"Journal of Algorithms"},{"key":"13_CR18","doi-asserted-by":"crossref","unstructured":"Gaur, D.R., Krishnamurti, R.: Average case self-duality of monotone boolean functions. In: Canadian AI 2004, pp. 322\u2013338 (2004)","DOI":"10.1007\/978-3-540-24840-8_23"},{"key":"13_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-24627-5_1","volume-title":"Foundations of Information and Knowledge Systems","author":"G. Gottlob","year":"2004","unstructured":"Gottlob, G.: Hypergraph transversals. In: Seipel, D., Turull-Torres, J.M.a. (eds.) FoIKS 2004. LNCS, vol.\u00a02942, pp. 1\u20135. Springer, Heidelberg (2004)"},{"key":"13_CR20","doi-asserted-by":"crossref","unstructured":"Gunopulos, D., Mannila, H., Khardon, R., Toivonen, H.: Data mining, hypergraph transversals, and machine learning (extended abstract). In: PODS 1997 (1997)","DOI":"10.1145\/263661.263684"},{"key":"13_CR21","doi-asserted-by":"crossref","unstructured":"Halman, N.: On the power of discrete and of lexicographic Helly-type theorems. In: FOCS 2004, pp. 463\u2013472 (2004)","DOI":"10.1109\/FOCS.2004.47"},{"issue":"1","key":"13_CR22","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1093\/comjnl\/bxm040","volume":"51","author":"F. H\u00fcffner","year":"2008","unstructured":"H\u00fcffner, F., Niedermeier, R., Wernicke, S.: Techniques for practical fixed-parameter algorithms. Comput. J.\u00a051(1), 7\u201325 (2008)","journal-title":"Comput. J."},{"issue":"7","key":"13_CR23","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 Trans. on Parallel and Distributed Systems\u00a04(7), 779\u2013794 (1993)","journal-title":"IEEE Trans. on Parallel and Distributed Systems"},{"key":"13_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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.H., 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":"13_CR25","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: Advances in Convex Analysis and Global Optimization, honoring the memory of K. Carath\u00e9odory, pp. 105\u2013118. Kluwer, Dordrecht (2000)"},{"key":"13_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1007\/11841036_41","volume-title":"Algorithms \u2013 ESA 2006","author":"L. Khachiyan","year":"2006","unstructured":"Khachiyan, L., Boros, E., Borys, K., Elbassioni, K., Gurvich, V., Makino, K.: Enumerating spanning and connected subsets in graphs and matroids. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 444\u2013455. Springer, Heidelberg (2006)"},{"issue":"4","key":"13_CR27","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/j.ipl.2006.09.006","volume":"101","author":"L. Khachiyan","year":"2007","unstructured":"Khachiyan, L., Boros, E., Elbassioni, K., Gurvich, V.: A global parallel algorithm for the hypergraph transversal problem. Information Processing Letters\u00a0101(4), 148\u2013155 (2007)","journal-title":"Information Processing Letters"},{"key":"13_CR28","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. Computing\u00a09, 558\u2013565 (1980)","journal-title":"SIAM J. Computing"},{"key":"13_CR29","unstructured":"Lov\u00e1sz, L.: Combinatorial optimization: some problems and trends. DIMACS Technical Report 92-53, Rutgers University (1992)"},{"issue":"2","key":"13_CR30","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/0022-0000(86)90015-2","volume":"33","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 Sciences\u00a033(2), 126\u2013141 (1986)","journal-title":"Journal of Computer and System Sciences"},{"key":"13_CR31","series-title":"Lecture Notes in Computer Science","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. Springer, Heidelberg (1997)"},{"key":"13_CR32","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1002\/net.1975.5.3.237","volume":"5","author":"R.C. Read","year":"1975","unstructured":"Read, R.C., Tarjan, R.E.: Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks\u00a05, 237\u2013252 (1975)","journal-title":"Networks"},{"key":"13_CR33","unstructured":"Tamaki, H.: Space-efficient enumeration of minimal transversals of a hypergraph. Technical Report IPSJ-AL 75 (2000)"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04128-0_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,22]],"date-time":"2020-05-22T05:14:23Z","timestamp":1590124463000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04128-0_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642041273","9783642041280"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04128-0_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}