{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T00:53:06Z","timestamp":1725583986253},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642387555"},{"type":"electronic","value":"9783642387562"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38756-2_30","type":"book-chapter","created":{"date-parts":[[2013,5,21]],"date-time":"2013-05-21T00:43:48Z","timestamp":1369097028000},"page":"294-302","source":"Crossref","is-referenced-by-count":1,"title":["Large Hypertree Width for Sparse Random Hypergraphs"],"prefix":"10.1007","author":[{"given":"Chaoyi","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tian","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ke","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"30_CR1","doi-asserted-by":"publisher","first-page":"2167","DOI":"10.1016\/j.ejc.2007.04.013","volume":"28","author":"I. Adler","year":"2007","unstructured":"Adler, I., Gottlob, G., Grohe, M.: Hypertree width and related hypergraph invariants. European Journal of Combinatorics\u00a028, 2167\u20132181 (2007)","journal-title":"European Journal of Combinatorics"},{"key":"30_CR2","unstructured":"Cheeseman, P., Kanefsky, R., Taylor, W.: Where the really hard problems are. IJCAI 1991, 163\u2013169 (1991)"},{"issue":"2","key":"30_CR3","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0304-3975(99)00220-0","volume":"239","author":"C. Chekuri","year":"2000","unstructured":"Chekuri, C., Rajaraman, A.: Conjunctive query containment revisited. Theoretical Computer Science\u00a0239(2), 211\u2013229 (2000)","journal-title":"Theoretical Computer Science"},{"key":"30_CR4","doi-asserted-by":"crossref","unstructured":"Cook, S.A., Mitchell, D.G.: Finding hard instances of the satisfiability problem: a survey. DIMACS Series, vol.\u00a035, pp. 1\u201317 (1997)","DOI":"10.1090\/dimacs\/035\/01"},{"key":"30_CR5","first-page":"276","volume-title":"Encyclopedia of Artificial Intelligence","author":"R. Dechter","year":"1992","unstructured":"Dechter, R.: Constraint networks. In: Encyclopedia of Artificial Intelligence, 2nd edn., vol.\u00a01, pp. 276\u2013285. Wiley and Sons, Chichester (1992)","edition":"2"},{"issue":"3","key":"30_CR6","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1016\/0004-3702(89)90037-4","volume":"38","author":"R. Dechter","year":"1989","unstructured":"Dechter, R., Pearl, J.: Tree clustering for constraint networks. Artificial Intelligence\u00a038(3), 353\u2013366 (1989)","journal-title":"Artificial Intelligence"},{"key":"30_CR7","doi-asserted-by":"publisher","first-page":"914","DOI":"10.1016\/j.artint.2010.11.004","volume":"175","author":"Y. Fan","year":"2011","unstructured":"Fan, Y., Shen, J.: On the phase transitions of random k-constraint satisfaction problems. Artificial Intelligence\u00a0175, 914\u2013927 (2011)","journal-title":"Artificial Intelligence"},{"key":"30_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.artint.2012.08.003","volume":"193","author":"Y. Fan","year":"2012","unstructured":"Fan, Y., Shen, J., Xu, K.: A general model and thresholds for random constraint satisfaction problems. Artificial Intelligence\u00a0193, 1\u201317 (2012)","journal-title":"Artificial Intelligence"},{"key":"30_CR9","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1613\/jair.2155","volume":"28","author":"Y. Gao","year":"2007","unstructured":"Gao, Y., Culberson, J.: Consistency and random constraint satisfaction problems. J. Artif. Intell. Res. (JAIR)\u00a028, 517\u2013557 (2007)","journal-title":"J. Artif. Intell. Res. (JAIR)"},{"key":"30_CR10","unstructured":"Gao, Y.: Phase transition of tractability in constraint satisfaction and Bayesian network inference. Proc. UAI, 265\u2013271 (2003)"},{"key":"30_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/11809678_25","volume-title":"Computing and Combinatorics","author":"Y. Gao","year":"2006","unstructured":"Gao, Y.: On the threshold of having a linear treewidth in random graphs. In: Chen, D.Z., Lee, D.T. (eds.) COCOON 2006. LNCS, vol.\u00a04112, pp. 226\u2013234. Springer, Heidelberg (2006)"},{"key":"30_CR12","unstructured":"Gao, Y.: Treewidth of Erd\u00f6s-R\u00e9nyi random graphs, random intersection graphs, and scale-free random graphs. CoRR abs\/0907.5481 (2009)"},{"key":"30_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/3-540-44683-4_5","volume-title":"Mathematical Foundations of Computer Science 2001","author":"G. Gottlob","year":"2001","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: Hypertree Decompositions: A Survey. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol.\u00a02136, p. 37. Springer, Heidelberg (2001)"},{"key":"30_CR14","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/S0004-3702(00)00078-3","volume":"124","author":"G. Gottlob","year":"2000","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: A comparison of structural CSP decomposition methods. Artificial Intelligence\u00a0124, 243\u2013282 (2000)","journal-title":"Artificial Intelligence"},{"key":"30_CR15","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: The complexity of acyclic conjunctive queries. Journal of ACM\u00a048(3), 431\u2013498","DOI":"10.1145\/382780.382783"},{"issue":"3","key":"30_CR16","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1006\/jcss.2001.1809","volume":"64","author":"G. Gottlob","year":"2002","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: Hypertree decomposition and tractable queries. Journal of Computer and System Sciences\u00a064(3), 579\u2013627 (2002)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"30_CR17","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0004-3702(94)90003-5","volume":"66","author":"M. Gyssens","year":"1994","unstructured":"Gyssens, M., Jeavons, P.G., Cohen, D.A.: Decomposition constraint satisfaction problems using database techniques. Artificial Intelligence\u00a066(1), 57\u201389 (1994)","journal-title":"Artificial Intelligence"},{"key":"30_CR18","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4615-9385-0_4","volume-title":"Advances in Data Base Theory","author":"M. Gyssens","year":"1984","unstructured":"Gyssens, M., Paredaens, J.: A decomposition methodology for cyclic databases. In: Gallaire, H., Nicolas, J.-M., Minker, J. (eds.) Advances in Data Base Theory, vol.\u00a02, pp. 85\u2013122. Plemum Press, New York (1984)"},{"key":"30_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/978-3-642-21204-8_26","volume-title":"Frontiers in Algorithmics and Algorithmic Aspects in Information and Management","author":"W. Jiang","year":"2011","unstructured":"Jiang, W., Liu, T., Ren, T., Xu, K.: Two hardness results on feedback vertex sets. In: Atallah, M., Li, X.-Y., Zhu, B. (eds.) FAW-AAIM 2011. LNCS, vol.\u00a06681, pp. 233\u2013243. Springer, Heidelberg (2011)"},{"key":"30_CR20","doi-asserted-by":"crossref","unstructured":"Kloks, T.: Treewidth: Computations and Approximations, page 18, 55. Springer (1994)","DOI":"10.1007\/BFb0045375"},{"key":"30_CR21","unstructured":"Lee, C., Lee, J., Oum, S.: Rank-width of random graphs. CoRR abs\/1001.0461 (2010)"},{"key":"30_CR22","unstructured":"Liu, T., Lin, X., Wang, C., Su, K., Xu, K.: Large Hinge Width on Sparse Random Hypergraphs. IJCAI 2011, 611\u2013616 (2011)"},{"key":"30_CR23","unstructured":"Mitchell, D.G., Selman, B., Levesque, H.J.: Hard and easy distributions of sat problems. In: Proc. AAAI, pp. 459\u2013465 (1992)"},{"key":"30_CR24","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/S1574-6526(06)80011-8","volume-title":"Handbook of Constraint Programming","author":"R. Dechter","year":"2006","unstructured":"Dechter, R.: Tractable Structures for Constraint Satisfaction Problems. In: Rossi, F., van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming, pp. 209\u2013244. Elsevier, Amsterdam (2006)"},{"key":"30_CR25","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0004-3702(95)00045-3","volume":"81","author":"B. Selman","year":"1996","unstructured":"Selman, B., Mitchell, D.G., Levesque, H.J.: Generating hard satisfiability problems. Artif. Intell.\u00a081, 17\u201329 (1996)","journal-title":"Artif. Intell."},{"key":"30_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1007\/978-3-642-22616-8_38","volume-title":"Combinatorial Optimization and Applications","author":"C. Wang","year":"2011","unstructured":"Wang, C., Liu, T., Cui, P., Xu, K.: A Note on Treewidth in Random Graphs. In: Wang, W., Zhu, X., Du, D.-Z. (eds.) COCOA 2011. LNCS, vol.\u00a06831, pp. 491\u2013499. Springer, Heidelberg (2011)"},{"key":"30_CR27","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1613\/jair.696","volume":"12","author":"K. Xu","year":"2000","unstructured":"Xu, K., Li, W.: Exact phase transitions in random constraint satisfaction problems. J. Artif. Intell. Res.\u00a012, 93\u2013103 (2000)","journal-title":"J. Artif. Intell. Res."},{"key":"30_CR28","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/j.tcs.2006.01.001","volume":"355","author":"K. Xu","year":"2006","unstructured":"Xu, K., Li, W.: Many hard examples in exact phase transitions. Theor. Comput. Sci.\u00a0355, 291\u2013302 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"30_CR29","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.artint.2007.04.001","volume":"171","author":"K. Xu","year":"2007","unstructured":"Xu, K., Boussemart, F., Hemery, F., Lecoutre, C.: Random Constraint Satisfaction: Easy Generation of Hard (Satisfiable) Instances. Artif. Intell.\u00a0171, 514\u2013534 (2007)","journal-title":"Artif. Intell."}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics and Algorithmic Aspects in Information and Management"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38756-2_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T03:07:57Z","timestamp":1557716877000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38756-2_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642387555","9783642387562"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38756-2_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}