{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T23:15:19Z","timestamp":1725578119044},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642190933"},{"type":"electronic","value":"9783642190940"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-19094-0_7","type":"book-chapter","created":{"date-parts":[[2011,2,10]],"date-time":"2011-02-10T06:21:40Z","timestamp":1297318900000},"page":"45-56","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of Acyclic Subhypergraph Problems"],"prefix":"10.1007","author":[{"given":"David","family":"Duris","sequence":"first","affiliation":[]},{"given":"Yann","family":"Strozecki","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"Beeri, C., Fagin, R., Maier, D., Mendelzon, A., Ullman, J., Yannakakis, M.: Properties of acyclic database schemes. In: Proceedings of the 13th Annual ACM Symposium on Theory of Computing, pp. 355\u2013362 (1981)","DOI":"10.1145\/800076.802489"},{"key":"7_CR2","volume-title":"Graphs and hypergraphs","author":"C. Berge","year":"1976","unstructured":"Berge, C.: Graphs and hypergraphs. North-Holland, Amsterdam (1976)"},{"key":"7_CR3","unstructured":"Brouwer, A.E., Kolen, A.W.J.: A super-balanced hypergraph has a nest point. Technical report, Stichting Mathematisch Centrum (1980)"},{"key":"7_CR4","doi-asserted-by":"crossref","unstructured":"Duris, D.: Hypergraph acyclicity and extension preservation theorems. In: Proceedings of the 23rd Annual IEEE Symposium on Logic in Computer Science, pp. 418\u2013427 (2008)","DOI":"10.1109\/LICS.2008.12"},{"issue":"3","key":"7_CR5","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1145\/2402.322390","volume":"30","author":"R. Fagin","year":"1983","unstructured":"Fagin, R.: Degrees of acyclicity for hypergraphs and relational database schemes. Journal of the ACM\u00a030(3), 514\u2013550 (1983)","journal-title":"Journal of the ACM"},{"key":"7_CR6","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1990","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1990)"},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"Goodall, A., de Mier, A.: Spanning trees of 3-uniform hypergraphs. Preprint available as arXiv:1002.3331v1 (February 2010)","DOI":"10.1016\/j.aam.2011.04.006"},{"key":"7_CR8","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195085914.001.0001","volume-title":"Limits to parallel computation: P-completeness theory","author":"R. Greenlaw","year":"1995","unstructured":"Greenlaw, R., Hoover, H.J., Ruzzo, W.L.: Limits to parallel computation: P-completeness theory. Oxford University Press, USA (1995)"},{"key":"7_CR9","first-page":"438","volume-title":"Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms","author":"S. Halperin","year":"1996","unstructured":"Halperin, S., Zwick, U.: Optimal randomized EREW PRAM algorithms for finding spanning forests and for other basic graph connectivity problems. In: Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 438\u2013447. SIAM, Philadelphia (1996)"},{"key":"7_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1007\/11537311_43","volume-title":"Fundamentals of Computation Theory","author":"K. Hirata","year":"2005","unstructured":"Hirata, K., Kuwabara, M., Harao, M.: On finding acyclic subhypergraphs. In: Li\u015bkiewicz, M., Reischuk, R. (eds.) FCT 2005. LNCS, vol.\u00a03623, pp. 491\u2013503. Springer, Heidelberg (2005)"},{"issue":"12","key":"7_CR11","doi-asserted-by":"publisher","first-page":"1209","DOI":"10.1016\/0031-8914(61)90063-5","volume":"27","author":"P.W. Kasteleyn","year":"1961","unstructured":"Kasteleyn, P.W.: The statistics of dimers on a lattice. Physica\u00a027(12), 1209\u20131225 (1961)","journal-title":"Physica"},{"issue":"2","key":"7_CR12","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/0095-8956(80)90066-0","volume":"28","author":"L. Lov\u00e1sz","year":"1980","unstructured":"Lov\u00e1sz, L.: Matroid matching and some applications. Journal of Combinatorial Theory, Series B\u00a028(2), 208\u2013236 (1980)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"7_CR13","unstructured":"Masbaum, G., Caracciolo, S., Sokal, A., Sportiello, A.: A randomized polynomial-time algorithm for the spanning hypertree problem on 3-uniform hypergraphs. Preprint available as arXiv:0812.3593"},{"key":"7_CR14","doi-asserted-by":"crossref","unstructured":"Masbaum, G., Vaintrob, A.: A new matrix-tree theorem. International Mathematics Research Notices\u00a0(27), 1397 (2002)","DOI":"10.1155\/S1073792802111044"},{"key":"7_CR15","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J. Schwartz","year":"1980","unstructured":"Schwartz, J.: Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM\u00a027, 701\u2013717 (1980)","journal-title":"Journal of the ACM"},{"issue":"2","key":"7_CR16","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1007\/BF02874424","volume":"44","author":"J. Wang","year":"2001","unstructured":"Wang, J., Li, H.: Counting acyclic hypergraphs. Science in China Series A: Mathematics\u00a044(2), 220\u2013224 (2001)","journal-title":"Science in China Series A: Mathematics"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-19094-0_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,18]],"date-time":"2021-11-18T19:58:24Z","timestamp":1637265504000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-19094-0_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642190933","9783642190940"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-19094-0_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}