{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T03:06:29Z","timestamp":1762916789660,"version":"3.40.5"},"reference-count":64,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2001,6,1]],"date-time":"2001-06-01T00:00:00Z","timestamp":991353600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2001,6,1]],"date-time":"2001-06-01T00:00:00Z","timestamp":991353600000},"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":["Artificial Intelligence Review"],"published-print":{"date-parts":[[2001,6]]},"DOI":"10.1023\/a:1011039901653","type":"journal-article","created":{"date-parts":[[2002,12,23]],"date-time":"2002-12-23T08:38:49Z","timestamp":1040632729000},"page":"243-267","source":"Crossref","is-referenced-by-count":9,"title":["Solution Techniques for Constraint Satisfaction Problems: Foundations"],"prefix":"10.1007","volume":"15","author":[{"given":"I.","family":"Miguel","sequence":"first","affiliation":[]},{"given":"Q.","family":"Shen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"246211_CR1","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/0004-3702(84)90008-0","volume":"23","author":"J. Allen","year":"1984","unstructured":"Allen, J. (1984). Toward a General Theory of Action and Time. Artificial Intelligence\n23(2): 123-154.","journal-title":"Artificial Intelligence"},{"key":"246211_CR2","unstructured":"Baker, A. B. (1994). The Hazards of Fancy Backtracking. In Proceedings of The 12th National Conference on Artificial Intelligence, 288-293."},{"key":"246211_CR3","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0004-3702(94)90041-8","volume":"65","author":"C. Bessiere","year":"1994","unstructured":"Bessiere, C. (1994). Arc-consistency and Arc-consistency Again, Artificial Intelligence\n65: 179-190.","journal-title":"Artificial Intelligence"},{"key":"246211_CR4","unstructured":"Bessiere, C., Freuder, E. C. & Regin, J. (1995). Using Inference to Reduce Arc Consistency Computation. In Proceedings of The 14th International Joint Conference on Artificial Intelligence, 592-598. Montreal, Quebec, Canada."},{"key":"246211_CR5","doi-asserted-by":"crossref","unstructured":"Bitner, R. & Reingold, M. (1975). Backtrack Programming Techniques. Communications of the ACM\n18(11).","DOI":"10.1145\/361219.361224"},{"issue":"1-2","key":"246211_CR6","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/S0004-3702(96)00047-1","volume":"90","author":"A. Blum","year":"1997","unstructured":"Blum, A. & Furst, M. (1997). Fast Planning through Planning Graph Analysis. Artificial Intelligence\n90(1-2): 281-300.","journal-title":"Artificial Intelligence"},{"key":"246211_CR7","unstructured":"Borning, A., Maher, M., Martindale, A. & Wilson, M. (1989). Constraint Hierarchies and Logic Programming. In Proceedings of The 6th International Conference on Logic Programming, 149-164."},{"key":"246211_CR8","unstructured":"Bruynooghe, M. (1985). Graph Coloring and Constraint Satisfaction, Technical Report CW-44. Department Computerwtenschappen, Kathioleke Universiteit Leuven."},{"key":"246211_CR9","doi-asserted-by":"crossref","unstructured":"Bruynooghe, M. (1985). Solving Combinatorial Search Problems by Intelligent Backtracking. Information Processing Letters\n12(1).","DOI":"10.1016\/0020-0190(81)90074-0"},{"key":"246211_CR10","unstructured":"Chmeiss, A. & Jegou, P. (1996). Path-Consistency: When Space Misses Time. In Proceedings of The 13th National Conference on Artificial Intelligence, 196-201. Portland, Oregon."},{"key":"246211_CR11","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/0004-3702(89)90080-5","volume":"41","author":"M. C. Cooper","year":"1989","unstructured":"Cooper, M. C. (1989). An Optimal k-Consistency Algorithm. Artificial Intelligence\n41: 89-95.","journal-title":"Artificial Intelligence"},{"key":"246211_CR12","unstructured":"Dechter, R. (1987). A Constraint-Network Approach to Truth-Maintenance, Technical Report R-80. Cognitive Systems Laboratory, Computer Science Department, University of California."},{"key":"246211_CR13","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0004-3702(90)90046-3","volume":"41","author":"R. Dechter","year":"1990","unstructured":"Dechter, R. (1990). Enhancement Schemes for Constraint Processing: Backjumping, Learning, and Cutset Decomposition. Artificial Intelligence\n41: 273-312.","journal-title":"Artificial Intelligence"},{"key":"246211_CR14","unstructured":"Dechter, R. (1992). Constraint Networks. In Encyclopedia of Artificial Intelligence, 276-285. John Wiley and Sons."},{"key":"246211_CR15","unstructured":"Dechter, R. & Dechter, A. (1988). Belief Maintenance in Dynamic Constraint Networks. In Proceedings of The 7th National Conference on Artificial Intelligence, 37-42. St Paul, Minnesota, USA."},{"key":"246211_CR16","unstructured":"Dechter, R. & Meiri, I. (1989). Experimental Evaluation of Preprocessing Techniques in Constraint Satisfaction Problems. In Proceedings of The 11th International Joint Conference on Artificial Intelligence, 271-277. Detroit, Michigan, USA."},{"key":"246211_CR17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0004-3702(87)90002-6","volume":"34","author":"R. Dechter","year":"1988","unstructured":"Dechter, R. & Pearl, J. (1988). Network-Based Heuristics for Constraint-Satisfaction Problems. Artificial Intelligence\n34: 1-38.","journal-title":"Artificial Intelligence"},{"key":"246211_CR18","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. Artificial Intelligence\n38: 353-366.","journal-title":"Artificial Intelligence"},{"key":"246211_CR19","unstructured":"Deville, Y. & van Hentenryck, P. (1991). An Efficient Arc Consistency Algorithm for a Class of CSP Problems. In Proceedings of The 12th International Joint Conference on Artificial Intelligence. Darling Harbour, Sydney, Australia."},{"key":"246211_CR20","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0004-3702(79)90008-0","volume":"12","author":"J. Doyle","year":"1979","unstructured":"Doyle, J. (1979). A Truth Maintenance System. Artificial Intelligence\n12: 231-272.","journal-title":"Artificial Intelligence"},{"key":"246211_CR21","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/S0004-3702(83)80012-5","volume":"21","author":"G. Fowler","year":"1983","unstructured":"Fowler, G., Haralick, R., Gray, F. G. & Feustel, C. (1983). Efficient Graph Automorphism by Vertex Partitioning. Artificial Intelligence\n21: 245-269.","journal-title":"Artificial Intelligence"},{"key":"246211_CR22","unstructured":"Fox, M. S. (1987). Constraint-Directed Search: A Case Study of Job-Shop Scheduling. Pitman, Morgan Kaufmann."},{"issue":"11","key":"246211_CR23","doi-asserted-by":"crossref","first-page":"958","DOI":"10.1145\/359642.359654","volume":"21","author":"E. C. Freuder","year":"1978","unstructured":"Freuder, E. C. (1978). Synthesizing Constraint Expressions. Communications of the ACM\n21(11): 958-966.","journal-title":"Communications of the ACM"},{"issue":"1","key":"246211_CR24","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1145\/322290.322292","volume":"29","author":"E. C. Freuder","year":"1982","unstructured":"Freuder, E. C. (1982). A Sufficient Condition for Backtrack-Free Search. Journal of the ACM\n29(1): 24-32.","journal-title":"Journal of the ACM"},{"key":"246211_CR25","unstructured":"Frost, D. & Dechter, R. (1994). Dead-End Driven Learning. In Proceedings of The 12th National Conference on Artificial Intelligence, 294-300."},{"key":"246211_CR26","unstructured":"Gaschnig, J. (1979). Performance Measurement and Analysis of Certain Search Algorithms, Technical Report. Department of Computer Science, Carnegie-Mellon University."},{"key":"246211_CR27","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1613\/jair.1","volume":"1","author":"M. L. Ginsberg","year":"1993","unstructured":"Ginsberg, M. L. (1993). Dynamic Backtracking. Journal of Artificial Intelligence Research\n1: 15-46.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"246211_CR28","doi-asserted-by":"crossref","unstructured":"Ginsberg, M. L. & McAllester, D. A. (1994). GSAT and Dynamic Backtracking. In Proceedings of The 4th International Conference on Principles of Knowledge Representation and Reasoning.","DOI":"10.1016\/B978-1-4832-1452-8.50117-2"},{"key":"246211_CR29","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0004-3702(88)90081-1","volume":"36","author":"C. Han","year":"1988","unstructured":"Han, C. & Lee, C. (1988). Comments on Mohr and Henderson's Path Consistency Algorithm. Artificial Intelligence\n36: 125-130.","journal-title":"Artificial Intelligence"},{"key":"246211_CR30","unstructured":"van Hentenryck, P (1989). Constraint Satisfaction in Logic Programming. MIT Press."},{"key":"246211_CR31","unstructured":"Jonsson, A. K. & Ginsberg, M. L. (1993). Experimenting with New Systematic and Nonsystematic Search Techniques. In Proceedings of The AAAI Symposium on AI and NPHard Problems."},{"key":"246211_CR32","unstructured":"de Kleer, J. (1989). A Comparison of ATMS and CSP Techniques. In Proceedings of The 11th International Joint Conference on Artificial Intelligence, 290-296. Detroit, Michigan, USA."},{"key":"246211_CR33","first-page":"295","volume-title":"Proceedings of The 4th International Conference on Principles and Practice of Constraint Programming","author":"T. H. Kolbe","year":"1998","unstructured":"Kolbe, T. H. (1998). Constraints for Object Recognition in Aerial Images-Handling of Unobserved Features. In Proceedings of The 4th International Conference on Principles and Practice of Constraint Programming, Lecture Notes in Computer Science 1520, 295-309. Pisa, Italy: Springer."},{"key":"246211_CR34","unstructured":"Kondrak, G. & van Beek, P. (1995). A Theoretical Evaluation of Selected Backtracking Algorithms. In Proceedings of The 14th International Joint Conference on Artificial Intelligence, 541-547. Montreal, Quebec, Canada."},{"key":"246211_CR35","doi-asserted-by":"crossref","unstructured":"Kuipers, B. (1994). Qualitative Reasoning: Modeling and Simulation with Incomplete Knowledge. MIT Press.","DOI":"10.1063\/1.4823391"},{"key":"246211_CR36","unstructured":"Kumar, V. (1992). Algorithms for Constraint Satisfaction Problems: A Survey. AI Magazine: 32-44."},{"key":"246211_CR37","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/0004-3702(91)90017-E","volume":"50","author":"D. McDermott","year":"1991","unstructured":"McDermott, D. (1991). A General Framework for Reason Maintenance. Artificial Intelligence\n50: 289-329.","journal-title":"Artificial Intelligence"},{"key":"246211_CR38","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0020-0255(79)90023-9","volume":"19","author":"J. McGregor","year":"1979","unstructured":"McGregor, J. (1979). Relational Consistency Algorithms and Their Applications in Finding Subgraph and Graph Isomorphism. Information Sciences\n19: 229-250.","journal-title":"Information Sciences"},{"issue":"1","key":"246211_CR39","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0004-3702(77)90007-8","volume":"8","author":"A. Mackworth","year":"1977","unstructured":"Mackworth, A. (1977). Consistency in Networks of Relations. Artificial Intelligence\n8(1); 99-118.","journal-title":"Artificial Intelligence"},{"key":"246211_CR40","unstructured":"Mackworth, A. (1977b). On Reading Sketch Maps. In Proceedings of The 5th International Joint Conference on Artificial Intelligence, 598-606, Cambridge, Massachusetts, USA."},{"key":"246211_CR41","unstructured":"Mackworth, A. (1992). Constraint Satisfaction Problems. In Encyclopedia of Artificial Intelligence, 285-293. John Wiley and Sons."},{"key":"246211_CR42","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/0004-3702(85)90041-4","volume":"25","author":"A. Mackworth","year":"1985","unstructured":"Mackworth, A. & Freuder, E. (1985). The Complexity of Some Polynomial Network-Consistency Algorithms for Constraint-Satisfaction Problems. Artificial Intelligence\n25: 65-74.","journal-title":"Artificial Intelligence"},{"issue":"1","key":"246211_CR43","doi-asserted-by":"crossref","first-page":"3","DOI":"10.3233\/AIC-1989-2101","volume":"2","author":"P. Meseguer","year":"1989","unstructured":"Meseguer, P. (1989). Constraint Satisfaction Problems: An Overview, AI Communications\n2(1): 3-17.","journal-title":"AI Communications"},{"key":"246211_CR44","first-page":"161","volume-title":"Proceedings of The 12th International Workshop on Qualitative Reasoning","author":"I. Miguel","year":"1998","unstructured":"Miguel, I. & Shen, Q. (1998). Extending Qualitative Modelling for Simulation of Time-Delayed Behaviour. In Proceedings of The 12th International Workshop on Qualitative Reasoning, 161-166. Cape Cod, Massachusetts, USA."},{"key":"246211_CR45","first-page":"267","volume":"15","author":"I. Miguel","year":"2001","unstructured":"Miguel, I. & Shen, Q. (2001). Solution Techniques for Constraint Satisfaction Problems: Advanced Approaches. Artificial Intelligence Review\n15: 267-291.","journal-title":"Artificial Intelligence Review"},{"key":"246211_CR46","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0004-3702(86)90083-4","volume":"28","author":"R. Mohr","year":"1986","unstructured":"Mohr, R. & Henderson, T. (1986). Arc and Path Consistency Revisited. Artificial Intelligence\n28: 225-233.","journal-title":"Artificial Intelligence"},{"key":"246211_CR47","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0020-0255(74)90008-5","volume":"7","author":"U. Montanari","year":"1974","unstructured":"Montanari, U. (1974). Networks of Constraints: Fundamental Properties and Applications to Picture Processing. Information Science\n7: 95-132.","journal-title":"Information Science"},{"key":"246211_CR48","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1111\/j.1467-8640.1989.tb00328.x","volume":"5","author":"B. A. Nadel","year":"1989","unstructured":"Nadel, B. A. (1989). Constraint Satisfaction Algorithms. Computational Intelligence\n5: 188-224.","journal-title":"Computational Intelligence"},{"key":"246211_CR49","unstructured":"Prosser, P. (1989). A Reactive Scheduling Agent. In Proceedings of The 11th International Joint Conference on Artificial Intelligence, 1004-1009. Detroit, Michigan, USA."},{"key":"246211_CR50","doi-asserted-by":"crossref","unstructured":"Prosser, P. (1993). Hybrid Algorithms for the Constraint Satisfaction Problem. Computational Intelligence\n9(1).","DOI":"10.1111\/j.1467-8640.1993.tb00310.x"},{"key":"246211_CR51","unstructured":"Rit, J. F. (1986). Propagating Temporal Constraints for Scheduling. In Proceedings of The 5th National Conference on Artificial Intelligence, 383-386, Philadelphia, Pennsylvania, USA."},{"key":"246211_CR52","first-page":"385","volume-title":"Proceedings of The 4th International Conference on Principles and Practice of Constraint Programming","author":"R. Rodosek","year":"1998","unstructured":"Rodosek, R. & Wallace, M. (1998). A Generic Model and Hybrid Algorithm for Hoist Scheduling Problems. In Proceedings of The 4th International Conference on Principles and Practice of Constraint Programming, Lecture Notes in Computer Science 1520, 385-399. Pisa, Italy: Springer."},{"key":"246211_CR53","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1109\/TSMC.1976.4309519","volume":"6","author":"A. Rosenfeld","year":"1976","unstructured":"Rosenfeld, A., Hummel, R. & Zucker, S. (1976). Scene Labeling by Relaxation Operations. IEEE Transactions on Systems, Man, and Cybernetics\n6: 420-433.","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics"},{"key":"246211_CR54","unstructured":"Schiex, T. & Verfaillie, T. (1994). Stubbornness: A Possible Enhancement for Backjumping and Nogood Recording. In Proceedings of The 11th European Conference on Artificial Intelligence, 165-169."},{"key":"246211_CR55","unstructured":"Schiex, T., Regin, J., Gaspin, C. & Verfaillie, G. (1996). Lazy Arc Consistency. In Proceedings of The 13th National Conference on Artificial Intelligence, 216-221. Portland, Oregon."},{"issue":"5","key":"246211_CR56","doi-asserted-by":"crossref","first-page":"504","DOI":"10.1109\/TPAMI.1981.4767144","volume":"3","author":"L. Shapiro","year":"1981","unstructured":"Shapiro, L. & Haralick, R. (1981). Structural Descriptions and Inexact Matching. IEEE Transactions on Pattern Analysis and Machine Intelligence\n3(5): 504-518.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"4","key":"246211_CR57","doi-asserted-by":"crossref","first-page":"1038","DOI":"10.1109\/21.247887","volume":"23","author":"Q. Shen","year":"1993","unstructured":"Shen, Q. & Leitch, R. (1993). Fuzzy Qualitative Simulation. IEEE Transactions on Systems, Man, and Cybernetics\n23(4): 1038-1061.","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics"},{"key":"246211_CR58","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0004-3702(77)90029-7","volume":"9","author":"R. M. Stallman","year":"1977","unstructured":"Stallman, R. M. & Sussman, G. J. (1977). Forward Reasoning and Dependency-Directed Backtracking in a System for Computer Aided Circuit Analysis. Artificial Intelligence\n9: 135-196.","journal-title":"Artificial Intelligence"},{"key":"246211_CR59","unstructured":"Tsang, E. P. K. (1987). The Consistent Labeling Problem in Temporal Reasoning. In Proceedings of The 6th National Conference on Artificial Intelligence, 251-255."},{"key":"246211_CR60","volume-title":"Foundations of Constraint Satisfaction","author":"E. P. K. Tsang","year":"1993","unstructured":"Tsang, E. P. K. (1993). Foundations of Constraint Satisfaction. Academic Press: London and San Diego."},{"key":"246211_CR61","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/321921.321925","volume":"23","author":"J. R. Ullman","year":"1976","unstructured":"Ullman, J. R. (1976). An Algorithm for Subgraph Isomorphism. Journal of the ACM\n23: 31-42.","journal-title":"Journal of the ACM"},{"key":"246211_CR62","unstructured":"Wallace, R. J. (1993). Why AC-3 is Almost Always Better than AC-4 for Establishing Arc Consistency in CSPs. In Proceedings of The 13th International Joint Conference on Artificial Intelligence, 239-245. Chamberg, France."},{"key":"246211_CR63","unstructured":"Waltz, D. (1975). Understanding Line Drawings of Scenes with Shadows. In Winston, P. H. (ed.) The Psychology of Computer Vision, 19-91. McGraw-Hill."},{"key":"246211_CR64","unstructured":"Zabih, R. & McAllester, D. (1988). A Rearrangement Strategy for Determining Propositional Satisfiability. In Proceedings of The 7th National Conference on Artificial Intelligence, 155-160. St Paul, Minnesota, USA."}],"container-title":["Artificial Intelligence Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1011039901653.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1011039901653\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1011039901653.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T04:38:44Z","timestamp":1747543124000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1011039901653"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,6]]},"references-count":64,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2001,6]]}},"alternative-id":["246211"],"URL":"https:\/\/doi.org\/10.1023\/a:1011039901653","relation":{},"ISSN":["0269-2821","1573-7462"],"issn-type":[{"type":"print","value":"0269-2821"},{"type":"electronic","value":"1573-7462"}],"subject":[],"published":{"date-parts":[[2001,6]]}}}