{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T05:40:07Z","timestamp":1746250807643,"version":"3.40.4"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319080154"},{"type":"electronic","value":"9783319080161"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-08016-1_25","type":"book-chapter","created":{"date-parts":[[2014,5,30]],"date-time":"2014-05-30T04:18:07Z","timestamp":1401423487000},"page":"276-287","source":"Crossref","is-referenced-by-count":0,"title":["A Study of Pure Random Walk Algorithms on Constraint Satisfaction Problems with Growing Domains"],"prefix":"10.1007","author":[{"given":"Wei","family":"Xu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fuzhou","family":"Gong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"25_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/BFb0017433","volume-title":"Principles and Practice of Constraint Programming - CP97","author":"D. Achlioptas","year":"1997","unstructured":"Achlioptas, D., Kirousis, L., Kranakis, E., Krizanc, D., Molloy, M., Stamatiou, Y.: Random constraint satisfaction: a more accurate picture. In: Smolka, G. (ed.) CP 1997. LNCS, vol.\u00a01330, pp. 107\u2013120. Springer, Heidelberg (1997)"},{"issue":"5","key":"25_CR2","doi-asserted-by":"publisher","first-page":"1248","DOI":"10.1137\/S0097539704440107","volume":"36","author":"M. Alekhnovich","year":"2006","unstructured":"Alekhnovich, M., Ben-Sasson, E.: Linear Upper Bounds for Random Walk on Small Density Random 3-cnfs. SIAM J. Comput.\u00a036(5), 1248\u20131263 (2006)","journal-title":"SIAM J. Comput."},{"key":"25_CR3","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1007\/978-3-540-85928-4_6","volume-title":"Inductive Logic Programming","author":"\u00c9. Alphonse","year":"2008","unstructured":"Alphonse, \u00c9., Osmani, A.: A model to study phase transition and plateaus in relational learning. In: \u017delezn\u00fd, F., Lavra\u010d, N. (eds.) ILP 2008. LNCS (LNAI), vol.\u00a05194, pp. 6\u201323. Springer, Heidelberg (2008)"},{"key":"25_CR4","unstructured":"Broder, A.Z., Frieze, A.M., Upfal, E.: On the Satisfiability and Maximum Satisfiability of Random 3-CNF Formulas. In: Proc of SODA, pp. 322\u2013330 (1993)"},{"issue":"4","key":"25_CR5","doi-asserted-by":"publisher","first-page":"1106","DOI":"10.1137\/0215080","volume":"15","author":"M. Chao","year":"1986","unstructured":"Chao, M., Franco, J.: Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem. SIAM J. Comput.\u00a015(4), 1106\u20131118 (1986)","journal-title":"SIAM J. Comput."},{"key":"25_CR6","doi-asserted-by":"crossref","unstructured":"Cocco, S., Monasson, R., Montanari, A., Semerjian, G.: Analyzing search algorithms with physical methods. In: Percus, A., Istrate, G., Moore, C. (eds.) Computational Complexity and Statistical Physics, pp. 63\u2013106. Oxford University Press (2006)","DOI":"10.1093\/oso\/9780195177374.003.0010"},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A., Frieze, A.: Analyzing Walksat on random formulas. In: Proc. of ANALCO, pp. 48\u201355 (2012)","DOI":"10.1137\/1.9781611973020.7"},{"key":"25_CR8","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A., Feige, U., Frieze, A., Krivelevich, M., Vilenchik, D.: On smoothed k-CNF formulas and the Walksat algorithm. In: Proc. of SODA, pp. 451\u2013460 (2009)","DOI":"10.1137\/1.9781611973068.50"},{"key":"25_CR9","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. Artif. Intell.\u00a0175, 914\u2013927 (2011)","journal-title":"Artif. Intell."},{"key":"25_CR10","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. Artif. Intell.\u00a0193, 1\u201317 (2012)","journal-title":"Artif. Intell."},{"key":"25_CR11","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.\u00a028, 517\u2013557 (2007)","journal-title":"J. Artif. Intell. Res."},{"issue":"4","key":"25_CR12","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1023\/A:1011454308633","volume":"6","author":"I. Gent","year":"2001","unstructured":"Gent, I., Macintype, E., Prosser, P., Smith, B., Walsh, T.: Random constraint satisfaction: flaws and structure. Constraints\u00a06(4), 345\u2013372 (2001)","journal-title":"Constraints"},{"key":"25_CR13","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":"25_CR14","doi-asserted-by":"crossref","unstructured":"Lecoutre, C.: Constraint Networks: Techniques and Algorithms. John Wiley & Sons (2009)","DOI":"10.1002\/9780470611821"},{"key":"25_CR15","unstructured":"Liu, T., Lin, X., Wang, C., Su, K., Xu, K.: Large Hinge Width on Sparse Random Hypergraphs. In: Proc of IJCAI, pp. 611\u2013616 (2011)"},{"key":"25_CR16","doi-asserted-by":"crossref","unstructured":"Liu, T., Wang, C., Xu, K.: Large hypertree width for sparse random hypergraphs. J. Comb. Optim. (2014), doi 10.1007\/s10878-013-9704-y","DOI":"10.1007\/s10878-013-9704-y"},{"key":"25_CR17","doi-asserted-by":"crossref","unstructured":"Mezard, M., Montanari, A.: Information, Physics and Computation. Oxford University Press (2009)","DOI":"10.1093\/acprof:oso\/9780198570837.001.0001"},{"key":"25_CR18","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1007\/978-3-540-74565-5_31","volume-title":"KI 2007: Advances in Artificial Intelligence","author":"S. Richter","year":"2007","unstructured":"Richter, S., Helmert, M., Gretton, C.: A stochastic local search approach to vertex cover. In: Hertzberg, J., Beetz, M., Englert, R. (eds.) KI 2007. LNCS (LNAI), vol.\u00a04667, pp. 412\u2013426. Springer, Heidelberg (2007)"},{"key":"25_CR19","unstructured":"Rossi, F., Van Beek, P., Walsh, T. (eds.): Handbook of Constraint Programming. Elsevier (2006)"},{"key":"25_CR20","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0004-3702(95)00052-6","volume":"81","author":"B.M. Smith","year":"1996","unstructured":"Smith, B.M., Dyer, M.E.: Locating the Phase Transition in Binary Constraint Satisfaction Problems. Artif. Intell.\u00a081, 155\u2013181 (1996)","journal-title":"Artif. Intell."},{"key":"25_CR21","doi-asserted-by":"crossref","unstructured":"Semerjian, G., Monasson, R.: Relaxation and Metastability in the Random Walk SAT search procedure. Phys. Rev. E 67, 066103 (2003)","DOI":"10.1103\/PhysRevE.67.066103"},{"key":"25_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/978-3-540-24605-3_10","volume-title":"Theory and Applications of Satisfiability Testing","author":"G. Semerjian","year":"2004","unstructured":"Semerjian, G., Monasson, R.: A Study of Pure Random Walk on Random Satisfiability Problems with Physical Methods. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol.\u00a02919, pp. 120\u2013134. Springer, Heidelberg (2004)"},{"key":"25_CR23","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1007\/s00453-001-0094-7","volume":"32","author":"U. Sch\u00f6ning","year":"2002","unstructured":"Sch\u00f6ning, U.: A probabilistic algorithm for k-SAT based on limited local search and restart. Algorithmica\u00a032, 615\u2013623 (2002)","journal-title":"Algorithmica"},{"key":"25_CR24","doi-asserted-by":"crossref","unstructured":"Sch\u00f6ning, U.: A probabilistic algorithm for k-SAT and constraint satisfaction problems. In: Proc. of FOCS, pp. 410\u2013414 (1999)","DOI":"10.1109\/SFFCS.1999.814612"},{"key":"25_CR25","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/S0304-3975(01)00166-9","volume":"265","author":"B. Smith","year":"2001","unstructured":"Smith, B.: Constructing an asymptotic phase transition in random binary constraint satisfaction problems. Theoret. Comput. Sci.\u00a0265, 265\u2013283 (2001)","journal-title":"Theoret. Comput. Sci."},{"key":"25_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":"25_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":"25_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. Theoret. Comput. Sci.\u00a0355, 291\u2013302 (2006)","journal-title":"Theoret. Comput. Sci."},{"key":"25_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."},{"key":"25_CR30","unstructured":"Xu, W.: An analysis of backtrack-free algorithm on a constraint satisfaction problem with growing domains (in Chineses). Acta Mathematicae Applicatae Sinica (Chinese Series) (accepted, 2014)"},{"key":"25_CR31","doi-asserted-by":"publisher","first-page":"985","DOI":"10.1016\/j.ipl.2011.07.006","volume":"111","author":"C. Zhao","year":"2011","unstructured":"Zhao, C., Zheng, Z.: Threshold behaviors of a random constraint satisfaction problem with exact phase transitions. Inform. Process. Lett.\u00a0111, 985\u2013988 (2011)","journal-title":"Inform. Process. Lett."},{"key":"25_CR32","doi-asserted-by":"crossref","unstructured":"Zhao, C., Zhang, P., Zheng, Z., Xu, K.: Analytical and Belief-propagation Studies of Random Constraint Satisfaction Problems with Growing Domains. Phys. Rev. E\u00a085, 016106 (2012)","DOI":"10.1103\/PhysRevE.85.016106"}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-08016-1_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T05:06:14Z","timestamp":1746248774000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-08016-1_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319080154","9783319080161"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-08016-1_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}