{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T03:35:47Z","timestamp":1742960147567,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":41,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540859574"},{"type":"electronic","value":"9783540859581"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-85958-1_20","type":"book-chapter","created":{"date-parts":[[2008,9,20]],"date-time":"2008-09-20T03:26:13Z","timestamp":1221881173000},"page":"298-312","source":"Crossref","is-referenced-by-count":2,"title":["From High Girth Graphs to Hard Instances"],"prefix":"10.1007","author":[{"given":"Carlos","family":"Ans\u00f3tegui","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ram\u00f3n","family":"B\u00e9jar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C\u00e9sar","family":"Fern\u00e0ndez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carles","family":"Mateu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"20_CR1","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1145\/972639.972645","volume":"51","author":"A. Atserias","year":"2004","unstructured":"Atserias, A.: On sufficient conditions for unsatisfiability of random formulas. Journal of the ACM\u00a051(2), 281\u2013311 (2004)","journal-title":"Journal of the ACM"},{"key":"20_CR2","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M., Razborov, A.: Lower bounds for polynomial calculus: non-binomial case. In: Proceedings of 42nd Annual Symposium on Foundations of Computer Science, pp. 190\u2013199 (2001)","DOI":"10.1109\/SFCS.2001.959893"},{"key":"20_CR3","unstructured":"Kahale, N.: Expander Graphs. PhD thesis. MIT (1993)"},{"key":"20_CR4","doi-asserted-by":"crossref","first-page":"1765","DOI":"10.1002\/j.1538-7305.1979.tb02972.x","volume":"58","author":"F.R.K. Chung","year":"1978","unstructured":"Chung, F.R.K.: On concentrators, superconcentrators, generalizers and nonblocking networks. Bell Systems Tech. Journal\u00a058, 1765\u20131777 (1978)","journal-title":"Bell Systems Tech. Journal"},{"issue":"6","key":"20_CR5","doi-asserted-by":"publisher","first-page":"1710","DOI":"10.1109\/18.556667","volume":"43","author":"M. Sipser","year":"1996","unstructured":"Sipser, M., Spielman, D.A.: Expander codes. IEEE Trans. on Information Theory\u00a043(6), 1710\u20131722 (1996)","journal-title":"IEEE Trans. on Information Theory"},{"key":"20_CR6","doi-asserted-by":"crossref","unstructured":"Charles, D.X., Goren, E.Z., Lauter, K.E.: Cryptographic hash functions from expander graphs. Journal of Cryptology (2007)","DOI":"10.1007\/s00145-007-9002-x"},{"key":"20_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1007\/3-540-61551-2_65","volume-title":"Principles and Practice of Constraint Programming - CP\u201996","author":"R. Bayardo","year":"1996","unstructured":"Bayardo, R., Schrag, R.: Using CSP look-back techniques to solve exceptionally hard sat instances. In: Freuder, E.C. (ed.) CP 1996. LNCS, vol.\u00a01118, pp. 46\u201360. Springer, Heidelberg (1996)"},{"issue":"1-3","key":"20_CR8","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s10817-005-9012-z","volume":"35","author":"Y. Boufkhad","year":"2005","unstructured":"Boufkhad, Y., Dubois, O., Interian, Y., Selman, B.: Regular random k-sat: Properties of balanced formulas. Journal of Automated Reasoning\u00a035(1-3), 181\u2013200 (2005)","journal-title":"Journal of Automated Reasoning"},{"key":"20_CR9","unstructured":"J\u00e4rvisalo, M.: Further investigations into regular xorsat. In: Proceedings of the AAAI 2006. AAAI Press \/ The MIT Press (2006)"},{"key":"20_CR10","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0004-3702(95)00052-6","volume":"81","author":"B. Smith","year":"1996","unstructured":"Smith, B., Dyer, M.: Locating the Phase Transition in Binary Constraint Satisfaction Problems. Artificial Intelligence\u00a081, 155\u2013181 (1996)","journal-title":"Artificial Intelligence"},{"issue":"4","key":"20_CR11","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1023\/A:1011454308633","volume":"6","author":"I. Gent","year":"2001","unstructured":"Gent, I., MacIntyre, E., Prosser, P., Smith, B., Walsh, T.: Random constraint satisfaction: flaws and structure. Constraints\u00a06(4), 345\u2013372 (2001)","journal-title":"Constraints"},{"key":"20_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1007\/BFb0017433","volume-title":"Principles and Practice of Constraint Programming - CP 1997","author":"D. Achlioptas","year":"1997","unstructured":"Achlioptas, D., Kirousis, L.M., Kranakis, E., Krizanc, D., Molloy, M.S.O., Stamatiou, Y.C.: Random Constraint Satisfaction: A More Accurate Picture. In: Smolka, G. (ed.) CP 1997. LNCS, vol.\u00a01330, pp. 107\u2013120. Springer, Heidelberg (1997)"},{"issue":"8-9","key":"20_CR13","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. Artificial Intelligence\u00a0171(8-9), 514\u2013534 (2007)","journal-title":"Artificial Intelligence"},{"key":"20_CR14","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/BF02126799","volume":"8","author":"A. Lubotzky","year":"1988","unstructured":"Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica\u00a08, 261\u2013277 (1988)","journal-title":"Combinatorica"},{"key":"20_CR15","doi-asserted-by":"crossref","first-page":"66","DOI":"10.37236\/1819","volume":"11","author":"B.D. McKay","year":"2004","unstructured":"McKay, B.D., Wormald, N.C., Wysocka, B.: Short cycles in random regular graphs. Elect. J. Combinatorics\u00a011, R66 (2004)","journal-title":"Elect. J. Combinatorics"},{"issue":"4\/5","key":"20_CR16","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/0020-0190(81)90050-8","volume":"13","author":"M. Blum","year":"1981","unstructured":"Blum, M., Karp, R., Vornberger, O., Papadimitriou, C., Yannakakis, M.: The complexity of testing whether a graph is a superconcentrator. Information Processing Letters\u00a013(4\/5), 164\u2013167 (1981)","journal-title":"Information Processing Letters"},{"issue":"5","key":"20_CR17","doi-asserted-by":"publisher","first-page":"1091","DOI":"10.1145\/210118.210136","volume":"42","author":"N. Kahale","year":"1995","unstructured":"Kahale, N.: Eigenvalues and expansion of regular graphs. Journal of the ACM\u00a042(5), 1091\u20131106 (1995)","journal-title":"Journal of the ACM"},{"issue":"2","key":"20_CR18","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1145\/375827.375835","volume":"48","author":"E. Ben-Sasson","year":"2001","unstructured":"Ben-Sasson, E., Wigderson, A.: Short proofs are narrow-resolution made simple. Journal of the ACM\u00a048(2), 149\u2013169 (2001)","journal-title":"Journal of the ACM"},{"key":"20_CR19","doi-asserted-by":"crossref","first-page":"026702","DOI":"10.1103\/PhysRevE.63.026702","volume":"63","author":"F. Ricci-Tersenghi","year":"2001","unstructured":"Ricci-Tersenghi, F., Weight, M., Zecchina, R.: Simplest random k-satisability problem. Physical Review E 63:026702 (2001)","journal-title":"Physical Review E"},{"key":"20_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/11527695_16","volume-title":"Proceedings of SAT 2005","author":"H. Jia","year":"2005","unstructured":"Jia, H., Moore, C., Selman, B.: From spin glasses to hard satisable formulas. In: Proceedings of SAT 2005. LNCS, vol.\u00a03452, pp. 199\u2013210. Springer, Heidelberg (2005)"},{"issue":"1-4","key":"20_CR21","doi-asserted-by":"crossref","first-page":"27","DOI":"10.3233\/SAT190015","volume":"2","author":"H. Haanp\u00e4\u00e4","year":"2006","unstructured":"Haanp\u00e4\u00e4, H., J\u00e4rvisalo, M., Kaski, P., Niemel\u00e4, I.: Hard satisfiable clause sets for benchmarking equivalence reasoning techniques. Journal on Satisfiability, Boolean Modeling and Computation\u00a02(1-4), 27\u201346 (2006)","journal-title":"Journal on Satisfiability, Boolean Modeling and Computation"},{"key":"20_CR22","volume-title":"Proceedings of the AAAI 2007","author":"C. Ans\u00f3tegui","year":"2007","unstructured":"Ans\u00f3tegui, C., B\u00e9jar, R., Fern\u00e1ndez, C., Mateu, C.: On balanced CSPs with high treewidth. In: Proceedings of the AAAI 2007. AAAI Press, Menlo Park (2007)"},{"issue":"4","key":"20_CR23","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/S0020-0190(03)00286-2","volume":"87","author":"L.S. Chandran","year":"2003","unstructured":"Chandran, L.S., Subramanian, C.: A spectral lower bound for the treewidth of a graph and its consequences. Information Processing Letters\u00a087(4), 195\u2013200 (2003)","journal-title":"Information Processing Letters"},{"key":"20_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1007\/3-540-46135-3_21","volume-title":"Principles and Practice of Constraint Programming - CP 2002","author":"V. Dalmau","year":"2002","unstructured":"Dalmau, V., Kolaitis, P.G., Vardi, M.Y.: Constraint satisfaction, bounded treewidth, and finite-variable logics. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol.\u00a02470, pp. 310\u2013326. Springer, Heidelberg (2002)"},{"key":"20_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/978-3-540-73420-8_26","volume-title":"Automata, Languages and Programming","author":"A. Atserias","year":"2007","unstructured":"Atserias, A., Bulatov, A.A., Dalmau, V.: On the power of k-consistency. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 279\u2013290. Springer, Heidelberg (2007)"},{"key":"20_CR26","doi-asserted-by":"crossref","unstructured":"Kautz, H.A., Ruan, Y., Achlioptas, D., Gomes, C.P., Selman, B., Stickel, M.E.: Balance and filtering in structured satisfiable problems. In: Proceedings of the IJCAI 2001, pp. 193\u2013200 (2001)","DOI":"10.1016\/S1571-0653(04)00310-5"},{"key":"20_CR27","unstructured":"Ans\u00f3tegui, C., B\u00e9jar, R., Fern\u00e1ndez, C., Gomes, C., Mateu, C.: The impact of balance in a highly structured problem domain. In: Proceedings of the AAAI 2006, pp. 438\u2013443. AAAI Press \/ The MIT Press (2006)"},{"issue":"3","key":"20_CR28","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1137\/S0895480101387893","volume":"16","author":"L.S. Chandran","year":"2003","unstructured":"Chandran, L.S.: A high girth graph construction. SIAM journal on Discrete Mathematics\u00a016(3), 366\u2013370 (2003)","journal-title":"SIAM journal on Discrete Mathematics"},{"key":"20_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1007\/11785293_36","volume-title":"Algorithm Theory \u2013 SWAT 2006","author":"J. Gudmundsson","year":"2006","unstructured":"Gudmundsson, J., Smid, M.: On spanners of geometric graphs. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol.\u00a04059, pp. 388\u2013399. Springer, Heidelberg (2006)"},{"issue":"4","key":"20_CR30","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1145\/1198513.1198519","volume":"2","author":"C. Demetrescu","year":"2006","unstructured":"Demetrescu, C., Italiano, G.F.: Experimental analysis of dynamic all pairs shortest path algorithms. ACM Transactions on Algorithms\u00a02(4), 578\u2013601 (2006)","journal-title":"ACM Transactions on Algorithms"},{"issue":"2","key":"20_CR31","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1006\/jagm.1996.0046","volume":"21","author":"G. Ramalingam","year":"1996","unstructured":"Ramalingam, G., Reps, T.: An incremental algorithm for a generalization of the shortest-path problem. Journal of Algorithms\u00a021(2), 267 (1996)","journal-title":"Journal of Algorithms"},{"key":"20_CR32","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithm Engineering","author":"C. Demetrescu","year":"2001","unstructured":"Demetrescu, C., Frigioni, D., Marchetti-Spaccamela, A., Nanni, U.: Maintaining shortest paths in digraphs with arbitrary arc weights: An experimental study. In: N\u00e4her, S., Wagner, D. (eds.) WAE 2000. LNCS, vol.\u00a01982. Springer, Heidelberg (2001)"},{"issue":"6","key":"20_CR33","doi-asserted-by":"crossref","first-page":"968","DOI":"10.1145\/1039488.1039492","volume":"51","author":"C. Demetrescu","year":"2004","unstructured":"Demetrescu, C., Italiano, G.: A new approach to dynamic all pairs shortest paths. Journal of the Association for Computing Machinery (JACM)\u00a051(6), 968\u2013992 (2004)","journal-title":"Journal of the Association for Computing Machinery (JACM)"},{"key":"20_CR34","doi-asserted-by":"crossref","unstructured":"Li, C.M.: Anbulagan: Look-ahead versus look-back for satisfiability problems. In: Principles and Practice of Constraint Programming, pp. 341\u2013355 (1997)","DOI":"10.1007\/BFb0017450"},{"key":"20_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1007\/978-3-540-24605-3_37","volume-title":"Theory and Applications of Satisfiability Testing","author":"N. E\u00e9n","year":"2004","unstructured":"E\u00e9n, N., S\u00f6rensson, N.: An extensible SAT-solver. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol.\u00a02919, pp. 502\u2013518. Springer, Heidelberg (2004)"},{"key":"20_CR36","unstructured":"Dubois, O., Dequen, G.: A backbone-search heuristic for efficient solving of hard 3-SAT formulae. In: Proceedings of the IJCAI 2001, pp. 248\u2013253 (2001)"},{"key":"20_CR37","unstructured":"Selman, B., Kautz, H.A., Cohen, B.: Noise strategies for improving local search. In: Proceedings of the AAAI 1994, pp. 337\u2013343 (1994)"},{"key":"20_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/978-3-540-72788-0_15","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2007","author":"C.M. Li","year":"2007","unstructured":"Li, C.M., Wei, W., Zhang, H.: Combining adaptive noise and look-ahead in local search for SAT. In: Marques-Silva, J., Sakallah, K.A. (eds.) SAT 2007. LNCS, vol.\u00a04501, pp. 121\u2013133. Springer, Heidelberg (2007)"},{"key":"20_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/3-540-46135-3_15","volume-title":"Principles and Practice of Constraint Programming - CP 2002","author":"W. Wei","year":"2002","unstructured":"Wei, W., Selman, B.: Accelerating random walks. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol.\u00a02470, pp. 216\u2013232. Springer, Heidelberg (2002)"},{"key":"20_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/11889205_15","volume-title":"Principles and Practice of Constraint Programming - CP 2006","author":"I.P. Gent","year":"2006","unstructured":"Gent, I.P., Jefferson, C., Miguel, I.: Watched literals for constraint propagation in minion. In: Benhamou, F. (ed.) CP 2006. LNCS, vol.\u00a04204, pp. 182\u2013197. Springer, Heidelberg (2006)"},{"key":"20_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/3-540-45349-0_32","volume-title":"Principles and Practice of Constraint Programming - CP 2000","author":"T. Walsh","year":"2000","unstructured":"Walsh, T.: SAT vs CSP. In: Dechter, R. (ed.) CP 2000. LNCS, vol.\u00a01894, pp. 441\u2013456. Springer, Heidelberg (2000)"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85958-1_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,9]],"date-time":"2024-05-09T07:04:50Z","timestamp":1715238290000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-85958-1_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540859574","9783540859581"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85958-1_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}