{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T04:52:50Z","timestamp":1751604770041},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2014,1,8]],"date-time":"2014-01-08T00:00:00Z","timestamp":1389139200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2015,4]]},"DOI":"10.1007\/s10878-013-9704-y","type":"journal-article","created":{"date-parts":[[2014,1,7]],"date-time":"2014-01-07T03:51:26Z","timestamp":1389066686000},"page":"531-540","source":"Crossref","is-referenced-by-count":6,"title":["Large hypertree width for sparse random hypergraphs"],"prefix":"10.1007","volume":"29","author":[{"given":"Tian","family":"Liu","sequence":"first","affiliation":[]},{"given":"Chaoyi","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Ke","family":"Xu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,1,8]]},"reference":[{"key":"9704_CR1","doi-asserted-by":"crossref","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 (2007) Hypertree width and related hypergraph invariants. Eur J Comb 28:2167\u20132181","journal-title":"Eur J Comb"},{"key":"9704_CR2","first-page":"163","volume":"1991","author":"P Cheeseman","year":"1991","unstructured":"Cheeseman P, Kanefsky R, Taylor W (1991) Where the really hard problems are. IJCAI 1991:163\u2013169","journal-title":"IJCAI"},{"issue":"2","key":"9704_CR3","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/S0304-3975(99)00220-0","volume":"239","author":"C Chekuri","year":"2000","unstructured":"Chekuri C, Rajaraman A (2000) Conjunctive query containment revisited. Theor Comput Sci 239(2):211\u2013229","journal-title":"Theor Comput Sci"},{"key":"9704_CR4","unstructured":"Cook SA, Mitchell DG (1997) Finding hard instances of the satisfiability problem: a survey. In: DIMACS series, vol 35, pp 1\u201317"},{"key":"9704_CR5","unstructured":"Dechter R (1992) Constraint networks. In: Encyclopedia of artificial intelligence, 2nd edn, vol 1, pp 276\u2013285. Wiley, Chichester"},{"key":"9704_CR6","doi-asserted-by":"crossref","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 (2006) Tractable structures for constraint satisfaction problems. In: Rossi F, van Beek P, Walsh T (eds) Handbook of constraint programming. Elsevier, Amsterdam, pp 209\u2013244"},{"issue":"3","key":"9704_CR7","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1016\/0004-3702(89)90037-4","volume":"38","author":"R Dechter","year":"1989","unstructured":"Dechter R, Pearl J (1989) Tree clustering for constraint networks. Artif Intell 38(3):353\u2013366","journal-title":"Artif Intell"},{"key":"9704_CR8","doi-asserted-by":"crossref","first-page":"914","DOI":"10.1016\/j.artint.2010.11.004","volume":"175","author":"Y Fan","year":"2011","unstructured":"Fan Y, Shen J (2011) On the phase transitions of random k-constraint satisfaction problems. Artif Intell 175:914\u2013927","journal-title":"Artif Intell"},{"key":"9704_CR9","doi-asserted-by":"crossref","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 (2012) A general model and thresholds for random constraint satisfaction problems. Artif Intell 193:1\u201317","journal-title":"Artif Intell"},{"key":"9704_CR10","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1007\/s10878-012-9492-9","volume":"25","author":"H Fu","year":"2013","unstructured":"Fu H, Huang K, Shiue C (2013) A note on optimal pebbling of hypercubes. J Comb Optim 25:597\u2013601","journal-title":"J Comb Optim"},{"key":"9704_CR11","unstructured":"Gao Y (2003) Phase transition of tractability in constraint satisfaction and Bayesian network inference. In: Proceedings of UAI, pp 265\u2013271"},{"key":"9704_CR12","first-page":"226","volume":"2006","author":"Y Gao","year":"2006","unstructured":"Gao Y (2006) On the threshold of having a linear treewidth in random graphs. COCOON 2006:226\u2013234","journal-title":"COCOON"},{"issue":"4\u20135","key":"9704_CR13","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1016\/j.dam.2011.10.013","volume":"160","author":"Y Gao","year":"2012","unstructured":"Gao Y (2012) Treewidth of Erd\u00f6s\u2013R\u00e9nyi random graphs, random intersection graphs, and scale-free random graphs. Discrete Appl Math 160(4\u20135):566\u2013578","journal-title":"Discrete Appl Math"},{"key":"9704_CR14","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1613\/jair.2155","volume":"28","author":"Y Gao","year":"2007","unstructured":"Gao Y, Culberson J (2007) Consistency and random constraint satisfaction problems. J Artif Intell Res (JAIR) 28:517\u2013557","journal-title":"J Artif Intell Res (JAIR)"},{"key":"9704_CR15","doi-asserted-by":"crossref","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 (2000) A comparison of structural CSP decomposition methods. Artif Intell 124:243\u2013282","journal-title":"Artif Intell"},{"key":"9704_CR16","doi-asserted-by":"crossref","unstructured":"Gottlob G, Leone N, Scarcello F (2001a) Hypertree decompositions: a survey. In: MFCS 2001, LNCS2136, pp 37\u201357","DOI":"10.1007\/3-540-44683-4_5"},{"issue":"3","key":"9704_CR17","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1145\/382780.382783","volume":"48","author":"G Gottlob","year":"2001","unstructured":"Gottlob G, Leone N, Scarcello F (2001b) The complexity of acyclic conjunctive queries. JACM 48(3):431\u2013498","journal-title":"JACM"},{"issue":"3","key":"9704_CR18","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1006\/jcss.2001.1809","volume":"64","author":"G Gottlob","year":"2002","unstructured":"Gottlob G, Leone N, Scarcello F (2002) Hypertree decomposition and tractable queries. J Comput Syst Sci 64(3):579\u2013627","journal-title":"J Comput Syst Sci"},{"key":"9704_CR19","doi-asserted-by":"crossref","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 (1984) A decomposition methodology for cyclic databases. In: Gallaire H, Nicolas J-M, Minker J (eds) Advances in data base theory, vol 2. Plemum Press, New York, pp 85\u2013122"},{"issue":"1","key":"9704_CR20","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0004-3702(94)90003-5","volume":"66","author":"M Gyssens","year":"1994","unstructured":"Gyssens M, Jeavons PG, Cohen DA (1994) Decomposition constraint satisfaction problems using database techniques. Artif Intell 66(1):57\u201389","journal-title":"Artif Intell"},{"key":"9704_CR21","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1007\/s10878-011-9439-6","volume":"26","author":"H Haviland","year":"2013","unstructured":"Haviland H (2013) Independent dominating sets in regular graphs. J Comb Optim 26:120\u2013126","journal-title":"J Comb Optim"},{"key":"9704_CR22","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1007\/s10878-011-9407-1","volume":"24","author":"S Hu","year":"2012","unstructured":"Hu S, Qi L (2012) Algebraic connectivity of an even uniform hypergraph. J Comb Optim 24:564\u2013579","journal-title":"J Comb Optim"},{"key":"9704_CR23","doi-asserted-by":"crossref","unstructured":"Jiang W, Liu T, Ren T, Xu K (2011) Two hardness results on feedback vertex sets. In: Proceedings of FAW-AAIM, LNCS 6681, pp 233\u2013243","DOI":"10.1007\/978-3-642-21204-8_26"},{"key":"9704_CR24","unstructured":"Kloks T (1994) Treewidth: computations and approximations. Springer, Berlin, pp 18, 55"},{"issue":"3","key":"9704_CR25","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1002\/jgt.20620","volume":"70","author":"C Lee","year":"2012","unstructured":"Lee C, Lee J, Oum S (2012) Rank-width of random graphs. J Graph Theory 70(3):339\u2013347","journal-title":"J Graph Theory"},{"key":"9704_CR26","doi-asserted-by":"crossref","first-page":"608","DOI":"10.1007\/s10878-012-9482-y","volume":"26","author":"CH Liu","year":"2013","unstructured":"Liu CH, Chang GJ (2013) Roman domination on strongly chordal graphs. J Comb Optim 26:608\u2013619","journal-title":"J Comb Optim"},{"key":"9704_CR27","first-page":"611","volume":"2011","author":"T Liu","year":"2011","unstructured":"Liu T, Lin X, Wang C, Su K, Xu K (2011) Large hinge width on sparse random hypergraphs. IJCAI 2011:611\u2013616","journal-title":"IJCAI"},{"key":"9704_CR28","unstructured":"Mitchell DG, Selman B, Levesque HJ (1992) Hard and easy distributions of sat problems. In: Proceedings of AAAI, pp 459\u2013465"},{"key":"9704_CR29","doi-asserted-by":"crossref","first-page":"770","DOI":"10.1007\/s10878-012-9483-x","volume":"26","author":"BS Panda","year":"2013","unstructured":"Panda BS, Pradhan D (2013) Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs. J Comb Optim 26:770\u2013785","journal-title":"J Comb Optim"},{"key":"9704_CR30","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0004-3702(95)00045-3","volume":"81","author":"B Selman","year":"1996","unstructured":"Selman B, Mitchell DG, Levesque HJ (1996) Generating hard satisfiability problems. Artif Intell 81:17\u201329","journal-title":"Artif Intell"},{"key":"9704_CR31","doi-asserted-by":"crossref","unstructured":"Wang C, Liu T, Cui P, Xu K (2011) A note on treewidth in random graphs. In: COCOA 2011, LNCS 6831, pp 491\u2013499","DOI":"10.1007\/978-3-642-22616-8_38"},{"key":"9704_CR32","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1613\/jair.696","volume":"12","author":"K Xu","year":"2000","unstructured":"Xu K, Li W (2000) Exact phase transitions in random constraint satisfaction problems. J Artif Intell Res 12:93\u2013103","journal-title":"J Artif Intell Res"},{"key":"9704_CR33","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/j.tcs.2006.01.001","volume":"355","author":"K Xu","year":"2006","unstructured":"Xu K, Li W (2006) Many hard examples in exact phase transitions. Theor Comput Sci 355:291\u2013302","journal-title":"Theor Comput Sci"},{"key":"9704_CR34","doi-asserted-by":"crossref","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 (2007) Random constraint satisfaction: easy generation of hard (satisfiable) instances. Artif Intell 171:514\u2013534","journal-title":"Artif Intell"},{"key":"9704_CR35","doi-asserted-by":"crossref","first-page":"016106","DOI":"10.1103\/PhysRevE.85.016106","volume":"85","author":"C Zhao","year":"2012","unstructured":"Zhao C, Zhang P, Zheng Z, Xu K (2012) Analytical and belief-propagation studies of random constraint satisfaction problems with growing domains. Phys Rev E 85:016106","journal-title":"Phys Rev E"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-013-9704-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-013-9704-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-013-9704-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,5]],"date-time":"2019-08-05T22:45:54Z","timestamp":1565045154000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-013-9704-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1,8]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,4]]}},"alternative-id":["9704"],"URL":"https:\/\/doi.org\/10.1007\/s10878-013-9704-y","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1,8]]}}}