{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T13:31:33Z","timestamp":1760707893546},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540748380"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74839-7_30","type":"book-chapter","created":{"date-parts":[[2007,12,6]],"date-time":"2007-12-06T14:55:58Z","timestamp":1196952958000},"page":"316-327","source":"Crossref","is-referenced-by-count":2,"title":["Lower Bounds for Three Algorithms for the Transversal Hypergraph Generation"],"prefix":"10.1007","author":[{"given":"Matthias","family":"Hagen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1-3","key":"30_CR1","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/s10107-003-0408-4","volume":"98","author":"E. Boros","year":"2003","unstructured":"Boros, E., Elbassioni, K.M., Gurvich, V., Khachiyan, L.: Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices. Mathematical Programming\u00a098(1-3), 355\u2013368 (2003)","journal-title":"Mathematical Programming"},{"key":"30_CR2","series-title":"North-Holland Mathematical Library","volume-title":"Hypergraphs","author":"C. Berge","year":"1989","unstructured":"Berge, C.: Hypergraphs. North-Holland Mathematical Library, vol.\u00a045. North-Holland, Amsterdam (1989)"},{"key":"30_CR3","first-page":"485","volume-title":"ICDM 2003","author":"J. Bailey","year":"2003","unstructured":"Bailey, J., Manoukian, T., Ramamohanarao, K.: A fast algorithm for computing hypergraph transversals and its application in mining emerging patterns. In: ICDM 2003. Proceedings of the 3rd IEEE International Conference on Data Mining, Melbourne, Florida, USA, 19-22 December 2003, pp. 485\u2013488. IEEE Computer Society, Los Alamitos (2003)"},{"issue":"3","key":"30_CR4","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/j.tcs.2005.10.004","volume":"351","author":"P. Damaschke","year":"2006","unstructured":"Damaschke, P.: Parameterized enumeration, transversals, and imperfect phylogeny reconstruction. Theoretical Computer Science\u00a0351(3), 337\u2013350 (2006)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"30_CR5","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1007\/s10115-004-0178-1","volume":"8","author":"G. Dong","year":"2005","unstructured":"Dong, G., Li, J.: Mining border descriptions of emerging patterns from dataset pairs. Knowledge and Information Systems\u00a08(2), 178\u2013202 (2005)","journal-title":"Knowledge and Information Systems"},{"issue":"6","key":"30_CR6","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 Journal on Computing\u00a024(6), 1278\u20131304 (1995)","journal-title":"SIAM Journal on Computing"},{"key":"30_CR7","series-title":"Lecture Notes in Artificial Intelligence","volume-title":"Logics in Artificial Intelligence","author":"T. Eiter","year":"2002","unstructured":"Eiter, T., Gottlob, G.: Hypergraph transversal computation and related problems in logic and AI. In: Flesca, S., Greco, S., Leone, N., Ianni, G. (eds.) JELIA 2002. LNCS (LNAI), vol.\u00a02424, Springer, Heidelberg (2002)"},{"key":"30_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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, Springer, Heidelberg (2006)"},{"issue":"3","key":"30_CR9","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(3), 618\u2013628 (1996)","journal-title":"Journal of Algorithms"},{"issue":"4","key":"30_CR10","doi-asserted-by":"publisher","first-page":"841","DOI":"10.1145\/4221.4223","volume":"32","author":"H. Garcia-Molina","year":"1985","unstructured":"Garcia-Molina, H., Barbar\u00e1, D.: How to assign votes in a distributed system. Journal of the ACM\u00a032(4), 841\u2013860 (1985)","journal-title":"Journal of the ACM"},{"issue":"1-3","key":"30_CR11","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/S0012-365X(96)00090-8","volume":"169","author":"V. Gurvich","year":"1997","unstructured":"Gurvich, V., Khachiyan, L.: On the frequency of the most frequently occurring variable in dual monotone DNFs. Discrete Mathematics\u00a0169(1-3), 245\u2013248 (1997)","journal-title":"Discrete Mathematics"},{"key":"30_CR12","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1145\/263661.263684","volume-title":"Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems","author":"D. Gunopulos","year":"1997","unstructured":"Gunopulos, D., Khardon, R., Mannila, H., Toivonen, H.: Data mining, hypergraph transversals, and machine learning. In: Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Tucson, Arizona, May 12-14, 1997, pp. 209\u2013216. ACM Press, New York (1997)"},{"issue":"3","key":"30_CR13","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., Papadimitriou, C.H., Yannakakis, M.: On generating all maximal independent sets. Information Processing Letters\u00a027(3), 119\u2013123 (1988)","journal-title":"Information Processing Letters"},{"issue":"2","key":"30_CR14","doi-asserted-by":"crossref","first-page":"239","DOI":"10.7155\/jgaa.00107","volume":"9","author":"D.J. Kavvadias","year":"2005","unstructured":"Kavvadias, D.J., Stavropoulos, E.C.: An efficient algorithm for the transversal hypergraph generation. Journal of Graph Algorithms and Applications\u00a09(2), 239\u2013264 (2005)","journal-title":"Journal of Graph Algorithms and Applications"},{"issue":"2","key":"30_CR15","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0166-218X(92)90031-5","volume":"40","author":"H. Mannila","year":"1992","unstructured":"Mannila, H., R\u00e4ih\u00e4, K.-J.: On the complexity of inferring functional dependencies. Discrete Applied Mathematics\u00a040(2), 237\u2013243 (1992)","journal-title":"Discrete Applied Mathematics"},{"key":"30_CR16","series-title":"Lecture Notes in Computer Science","volume-title":"Automata, Languages and Programming","author":"C.H. Papadimitriou","year":"1997","unstructured":"Papadimitriou, C.H.: NP-completeness: A retrospective. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) ICALP 1997. LNCS, vol.\u00a01256, Springer, Heidelberg (1997)"},{"issue":"2","key":"30_CR17","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1109\/25.669084","volume":"47","author":"S. Sarkar","year":"1998","unstructured":"Sarkar, S., Sivarajan, K.N.: Hypergraph models for cellular mobile communication systems. IEEE Transactions on Vehicular Technology\u00a047(2), 460\u2013471 (1998)","journal-title":"IEEE Transactions on Vehicular Technology"},{"key":"30_CR18","unstructured":"Takata, K.: On the sequential method for listing minimal hitting sets. In: Proceedings Workshop on Discrete Mathematics and Data Mining. 2nd SIAM International Conference on Data Mining, Arlington, Virginia, USA, April 11-13, 2002, pp. 109\u2013120 (2002)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74839-7_30.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:42:35Z","timestamp":1619520155000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74839-7_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540748380"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74839-7_30","relation":{},"subject":[]}}