{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:37:47Z","timestamp":1762101467882},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642406263"},{"type":"electronic","value":"9783642406270"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40627-0_22","type":"book-chapter","created":{"date-parts":[[2013,9,7]],"date-time":"2013-09-07T07:11:01Z","timestamp":1378537861000},"page":"263-272","source":"Crossref","is-referenced-by-count":7,"title":["Dead-End Elimination for Weighted CSP"],"prefix":"10.1007","author":[{"given":"Simon","family":"de Givry","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Steven D.","family":"Prestwich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Barry","family":"O\u2019Sullivan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"22_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"840","DOI":"10.1007\/978-3-642-33558-7_60","volume-title":"Principles and Practice of Constraint Programming","author":"D. Allouche","year":"2012","unstructured":"Allouche, D., Traor\u00e9, S., Andr\u00e9, I., de Givry, S., Katsirelos, G., Barbe, S., Schiex, T.: Computational protein design as a cost function network optimization problem. In: Milano, M. (ed.) CP 2012. LNCS, vol.\u00a07514, pp. 840\u2013849. Springer, Heidelberg (2012)"},{"issue":"3","key":"22_CR2","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1023\/A:1026488509554","volume":"4","author":"E. Bensana","year":"1999","unstructured":"Bensana, E., Lema\u00eetre, M., Verfaillie, G.: Earth observation satellite management. Constraints\u00a04(3), 293\u2013299 (1999)","journal-title":"Constraints"},{"key":"22_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/3-540-46135-3_53","volume-title":"Principles and Practice of Constraint Programming - CP 2002","author":"S. Bistarelli","year":"2002","unstructured":"Bistarelli, S., Faltings, B.V., Neagu, N.: Interchangeability in Soft CSPs. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol.\u00a02470, pp. 31\u201346. Springer, Heidelberg (2002)"},{"key":"22_CR4","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1023\/A:1009812409930","volume":"4","author":"B. Cabon","year":"1999","unstructured":"Cabon, B., de Givry, S., Lobjois, L., Schiex, T., Warners, J.: Radio link frequency assignment. Constraints Journal\u00a04, 79\u201389 (1999)","journal-title":"Constraints Journal"},{"issue":"1","key":"22_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10601-011-9112-9","volume":"17","author":"G. Chu","year":"2012","unstructured":"Chu, G., Banda, M., Stuckey, P.: Exploiting subproblem dominance in constraint programming. Constraints\u00a017(1), 1\u201338 (2012)","journal-title":"Constraints"},{"key":"22_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1007\/978-3-642-33558-7_4","volume-title":"Principles and Practice of Constraint Programming","author":"G. Chu","year":"2012","unstructured":"Chu, G., Stuckey, P.J.: A generic method for identifying and exploiting dominance relations. In: Milano, M. (ed.) CP 2012. LNCS, vol.\u00a07514, pp. 6\u201322. Springer, Heidelberg (2012)"},{"key":"22_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"680","DOI":"10.1007\/11889205_50","volume-title":"Principles and Practice of Constraint Programming - CP 2006","author":"M. Cooper","year":"2006","unstructured":"Cooper, M., Cussat-Blanc, S., de Roquemaurel, M., R\u00e9gnier, P.: Soft arc consistency applied to optimal planning. In: Benhamou, F. (ed.) CP 2006. LNCS, vol.\u00a04204, pp. 680\u2013684. Springer, Heidelberg (2006)"},{"key":"22_CR8","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1016\/j.artint.2010.02.001","volume":"174","author":"M. Cooper","year":"2010","unstructured":"Cooper, M., de Givry, S., Sanchez, M., Schiex, T., Zytnicki, M., Werner, T.: Soft arc consistency revisited. Artificial Intelligence\u00a0174, 449\u2013478 (2010)","journal-title":"Artificial Intelligence"},{"key":"22_CR9","unstructured":"Cooper, M., de Givry, S., Sanchez, M., Schiex, T., Zytnicki, M.: Virtual arc consistency for weighted CSP. In: Proc. of AAAI 2008, Chicago, IL (2008)"},{"key":"22_CR10","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/s10601-005-2240-3","volume":"10","author":"M.C. Cooper","year":"2005","unstructured":"Cooper, M.C.: High-order consistency in Valued Constraint Satisfaction. Constraints\u00a010, 283\u2013305 (2005)","journal-title":"Constraints"},{"key":"22_CR11","unstructured":"Cooper, M.C., de Givry, S., Schiex, T.: Optimal soft arc consistency. In: Proc. of IJCAI 2007, Hyderabad, India, pp. 68\u201373 (January 2007)"},{"issue":"1-2","key":"22_CR12","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/j.artint.2003.09.002","volume":"154","author":"M.C. Cooper","year":"2004","unstructured":"Cooper, M.C., Schiex, T.: Arc consistency for soft constraints. Artificial Intelligence\u00a0154(1-2), 199\u2013227 (2004)","journal-title":"Artificial Intelligence"},{"issue":"5","key":"22_CR13","doi-asserted-by":"publisher","first-page":"895","DOI":"10.1002\/pro.5560050511","volume":"5","author":"B. Dahiyat","year":"1996","unstructured":"Dahiyat, B., Mayo, S.: Protein design automation. Protein Science\u00a05(5), 895\u2013903 (1996)","journal-title":"Protein Science"},{"issue":"6369","key":"22_CR14","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1038\/356539a0","volume":"356","author":"J. Desmet","year":"1992","unstructured":"Desmet, J., Maeyer, M., Hazes, B., Lasters, I.: The dead-end elimination theorem and its use in protein side-chain positioning. Nature\u00a0356(6369), 539\u2013542 (1992)","journal-title":"Nature"},{"key":"22_CR15","unstructured":"Freuder, E.C.: Eliminating interchangeable values in constraint satisfaction problems. In: Proc. of AAAI 1991, Anaheim, CA, pp. 227\u2013233 (1991)"},{"issue":"14","key":"22_CR16","doi-asserted-by":"crossref","first-page":"e174","DOI":"10.1093\/bioinformatics\/btl220","volume":"22","author":"I. Georgiev","year":"2006","unstructured":"Georgiev, I., Lilien, R., Donald, B.: Improved pruning algorithms and divide-and-conquer strategies for dead-end elimination, with application to protein design. Bioinformatics 22(14), e174\u2013e183 (2006)","journal-title":"Bioinformatics"},{"issue":"5","key":"22_CR17","doi-asserted-by":"publisher","first-page":"1335","DOI":"10.1016\/S0006-3495(94)80923-3","volume":"66","author":"R. Goldstein","year":"1994","unstructured":"Goldstein, R.: Efficient rotamer elimination applied to protein side-chains and related spin glasses. Biophysical Journal\u00a066(5), 1335\u20131340 (1994)","journal-title":"Biophysical Journal"},{"key":"22_CR18","unstructured":"Harvey, W.D., Ginsberg, M.L.: Limited discrepency search. In: Proc. of the 14th IJCAI, Montr\u00e9al, Canada (1995)"},{"issue":"3","key":"22_CR19","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1016\/j.ejor.2010.11.008","volume":"212","author":"A. Jouglet","year":"2011","unstructured":"Jouglet, A., Carlier, J.: Dominance rules in combinatorial optimization problems. European Journal of Operational Research\u00a0212(3), 433\u2013444 (2011)","journal-title":"European Journal of Operational Research"},{"key":"22_CR20","unstructured":"Koster, A.M.C.A.: Frequency assignment: Models and Algorithms. Ph.D. thesis, University of Maastricht, The Netherlands (November 1999), \n                    \n                      www.zib.de\/koster\/thesis.html"},{"key":"22_CR21","unstructured":"Larrosa, J.: On arc and node consistency in weighted CSP. In: Proc. AAAI 2002, Edmondton (CA), pp. 48\u201353 (2002)"},{"key":"22_CR22","unstructured":"Larrosa, J., de Givry, S., Heras, F., Zytnicki, M.: Existential arc consistency: getting closer to full arc consistency in weighted CSPs. In: Proc. of the 19th IJCAI, Edinburgh, Scotland, pp. 84\u201389 (August 2005)"},{"issue":"2-3","key":"22_CR23","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1016\/j.artint.2007.05.006","volume":"172","author":"J. Larrosa","year":"2008","unstructured":"Larrosa, J., Heras, F., de Givry, S.: A logical approach to efficient max-sat solving. Artif. Intell.\u00a0172(2-3), 204\u2013233 (2008)","journal-title":"Artif. Intell."},{"issue":"1-2","key":"22_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.artint.2004.05.004","volume":"159","author":"J. Larrosa","year":"2004","unstructured":"Larrosa, J., Schiex, T.: Solving weighted CSP by maintaining arc consistency. Artif. Intell.\u00a0159(1-2), 1\u201326 (2004)","journal-title":"Artif. Intell."},{"key":"22_CR25","doi-asserted-by":"publisher","first-page":"1592","DOI":"10.1016\/j.artint.2009.09.002","volume":"173","author":"C. Lecoutre","year":"2009","unstructured":"Lecoutre, C., Sa\u00efs, L., Tabary, S., Vidal, V.: Reasoning from last conflict(s) in constraint programming. Artificial Intelligence\u00a0173, 1592\u20131614 (2009)","journal-title":"Artificial Intelligence"},{"key":"22_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1007\/978-3-642-33558-7_31","volume-title":"Principles and Practice of Constraint Programming","author":"C. Lecoutre","year":"2012","unstructured":"Lecoutre, C., Roussel, O., Dehani, D.E.: WCSP Integration of Soft Neighborhood Substitutability. In: Milano, M. (ed.) CP 2012. LNCS, vol.\u00a07514, pp. 406\u2013421. Springer, Heidelberg (2012)"},{"key":"22_CR27","doi-asserted-by":"crossref","unstructured":"Leyton-Brown, K., Pearson, M., Shoham, Y.: Towards a Universal Test Suite for Combinatorial Auction Algorithms. In: ACM E-Commerce, pp. 66\u201376 (2000)","DOI":"10.1145\/352871.352879"},{"issue":"1","key":"22_CR28","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1006\/jmbi.2000.4424","volume":"307","author":"L. Looger","year":"2001","unstructured":"Looger, L., Hellinga, H.: Generalized dead-end elimination algorithms make large-scale protein side-chain structure prediction tractable: implications for protein design and structural genomics. Journal of Molecular Biology\u00a0307(1), 429\u2013445 (2001)","journal-title":"Journal of Molecular Biology"},{"issue":"1","key":"22_CR29","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1006\/jagm.2000.1075","volume":"36","author":"R. Niedermeier","year":"2000","unstructured":"Niedermeier, R., Rossmanith, P.: New upper bounds for maximum satisfiability. J. Algorithms\u00a036(1), 63\u201388 (2000)","journal-title":"J. Algorithms"},{"issue":"11","key":"22_CR30","doi-asserted-by":"publisher","first-page":"999","DOI":"10.1002\/1096-987X(200008)21:11<999::AID-JCC9>3.0.CO;2-A","volume":"21","author":"N. Pierce","year":"2000","unstructured":"Pierce, N., Spriet, J., Desmet, J., Mayo, S.: Conformational splitting: A more powerful criterion for dead-end elimination. Journal of Computational Chemistry\u00a021(11), 999\u20131009 (2000)","journal-title":"Journal of Computational Chemistry"},{"key":"22_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/3-540-45349-0_30","volume-title":"Principles and Practice of Constraint Programming - CP 2000","author":"T. Schiex","year":"2000","unstructured":"Schiex, T.: Arc consistency for soft constraints. In: Dechter, R. (ed.) CP 2000. LNCS, vol.\u00a01894, pp. 411\u2013424. Springer, Heidelberg (2000)"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40627-0_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,17]],"date-time":"2019-05-17T02:02:55Z","timestamp":1558058575000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40627-0_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642406263","9783642406270"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40627-0_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}