A Sufficient Condition for Backtrack-Free Search

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A Sufficient Condition for Backtrack-Free Search

Full text

Pdf (508 KB)

Source

Journal of the ACM (JACM) archive
Volume 29 , Issue 1 (January 1982) table of contents

Pages: 24 - 32

Year of Publication: 1982

ISSN:0004-5411

Author

Eugene C. Freuder

Department of Computer Science, University of New Hampshire, Durham, New Hampshire

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 90, Citation Count: 92

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/322290.322292 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
	2	James R. Bitner , Edward M. Reingold, Backtrack programming techniques, Communications of the ACM, v.18 n.11, p.651-656, Nov. 1975 [doi>10.1145/361219.361224]
	3	Daniel G. Bobrow , Bertram Raphael, New Programming Languages for Artificial Intelligence Research, ACM Computing Surveys (CSUR), v.6 n.3, p.153-174, Sept. 1974 [doi>10.1145/356631.356632]
	4	Eugene C. Freuder, Synthesizing constraint expressions, Communications of the ACM, v.21 n.11, p.958-966, Nov. 1978 [doi>10.1145/359642.359654]
	5	GASCHNIG, J Experimental case studies of backtrack vs Waltz-type vs new algor,thms for satlsficmg assignment problems. Proc. 2rid Nat Conf of the Canadxan Society for Computat,onal Studies of Intelligence, Toronto, Ontano, 1978, pp. 268-277
	6	KNUTH, D E. Estlmattng the efficiency of backtrack programs Math. Comput 29 (Jan 1975), 121-136.
	7	MACKWORTH, A.K Consistency in networks of relations Artif. Intell. 8 (1977), 99-118
	8	MATULA, D.W A ram-max theorem for graphs with apphcation to graph coloring SlAM Rev I0 (1968), 481-482
	9	MATULA, O W, MARBLE, G, Arid ISAACSON, J.D Graph coloring algorithms In Graph Theory and Computing, R C Read, Ed, Academtc Press, New York, 1972, pp 109-122
	10	Nils J. Nilsson, Problem-Solving Methods in Artificial Intelligence, McGraw-Hill Pub. Co., 1971
	11	PURDOM, P W.Tree size by partial backtracking. SIAM d. Comput 7 (1978), 481-491.
	12	SZEKERES, G., AND WILF, H S.Aa mequahty for the chromatic number of a graph J Comb Theory 4 (1968), 1-3.
	13	TENENBAUM, J M, AND BARROW, H.G IGS A paradigm for mtegraUng image segmentation and interpretation. In Pattern Recogmtton and Artificial lntelhgence, C.H. Chen, Ed. Academic Press, New York, 1976, pp 472-507
	14	WALTZ, D.L Understanding line drawmgs of scenes with shadows. In The Psychology of Computer Vision, P H Winston, Ed, McGraw-Hall, New York, 1975, pp 19-91.
	15	WELLS, M B. Elements of Combinatorial Computing Pergamon Press, New York, 1971.
	16	Niklaus Wirth, Algorithms & data structures, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985

CITED BY 92

	Marek Perkowski , Rahul Malvi , Stan Grygiel , Mike Burns , Alan Mishchenko, Graph coloring algorithms for fast evaluation of Curtis decompositions, Proceedings of the 36th ACM/IEEE conference on Design automation, p.225-230, June 21-25, 1999, New Orleans, Louisiana, United States
	R. Dechter, Decomposing an N-ary relation into a tree of binary relations, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.185-189, March 23-25, 1987, San Diego, California, United States
	Wesley W. Chu , Patrick Ngai, A dynamic constraint-directed ordered search algorithm for solving constraint satisfaction problems, Proceedings of the 1st international conference on Industrial and engineering applications of artificial intelligence and expert systems, p.116-125, June 1988, Tullahoma, Tennessee, United States
	R. Dechter, Bucket elimination: a unifying framework for processing hard and soft constraints, ACM Computing Surveys (CSUR), v.28 n.4es, Dec. 1996
	Moshe Y. Vardi, Constraint satisfaction and database theory: a tutorial, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.76-85, May 15-18, 2000, Dallas, Texas, United States
	Rina Dechter , Daniel Frost, Backjump-based backtracking for constraint satisfaction problems, Artificial Intelligence, v.136 n.2, p.147-188, April 2002
	Peter van Beek , Rina Dechter, Constraint tightness and looseness versus local and global consistency, Journal of the ACM (JACM), v.44 n.4, p.549-566, July 1997
	Pascal Van Hentenryck , Vijay Saraswat, Strategic directions in constraint programming, ACM Computing Surveys (CSUR), v.28 n.4, p.701-726, Dec. 1996
	Lawrence F. Arnstein , Don Thomas, A general consistency technique for increasing the controllability of high level synthesis tools, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.741-744, November 07-11, 1993, Santa Clara, California, United States
	Philippe Jégou , Cyril Terrioux, Hybrid backtracking bounded by tree-decomposition of constraint networks, Artificial Intelligence, v.146 n.1, p.43-75, May 2003
	Eugene C. Freuder, A sufficient condition for backtrack-bounded search, Journal of the ACM (JACM), v.32 n.4, p.755-761, Oct. 1985
	Robert Allen , Luigi Cinque , Steven Tanimoto , Linda Shapiro , Dean Yasuda, A Parallel Algorithm for Graph Matching and Its MasPar Implementation, IEEE Transactions on Parallel and Distributed Systems, v.8 n.5, p.490-501, May 1997
	Hans Werner Guesgen, Towards a compiler for a constraint language, Proceedings of the 2nd international conference on Industrial and engineering applications of artificial intelligence and expert systems, p.262-269, June 1989, Tullahoma, Tennessee, United States
	James F. Allen, Maintaining knowledge about temporal intervals, Communications of the ACM, v.26 n.11, p.832-843, Nov. 1983
	Martin Dyer , Alan Frieze , Michael Molloy, A probabilistic analysis of randomly generated binary constraint satisfaction problems, Theoretical Computer Science, v.290 n.3, p.1815-1828, 3 January 2003
	Manolis Koubarakis, Tractable disjunctions of linear constraints: basic results and applications to temporal reasoning, Theoretical Computer Science, v.266 n.1-2, p.311-339, 09/06/2001
	Samnuk Keretho , Rasiah Loganantharaj, Qualitative and quantitative time interval constraint networks, Proceedings of the 19th annual conference on Computer Science, p.239-246, April 1991, San Antonio, Texas, United States
	Frédéric Bes , Cécile Roisin, A presentation language for controlling the formatting process in multimedia presentations, Proceedings of the 2002 ACM symposium on Document engineering, November 08-09, 2002, McLean, Virginia, USA
	Rina Dechter , Irina Rish, Mini-buckets: A general scheme for bounded inference, Journal of the ACM (JACM), v.50 n.2, p.107-153, March 2003
	Hans W. Guesgen, Fuzzifying spatial relations, Applying soft computing in defining spatial relations, Physica-Verlag GmbH, Heidelberg, Germany, 2002
	Gilles Chabert , Gilles Trombettoni , Bertrand Neveu, Box-set consistency for interval-based constraint problems, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
	Yuanlin Zhang , Roland H. C. Yap, Consistency and set intersection, Eighteenth national conference on Artificial intelligence, p.971-972, July 28-August 01, 2002, Edmonton, Alberta, Canada
	Vipin Kumar, Integrating knowledge in problem solving search procedures, Proceedings of the 1984 annual conference of the ACM on The fifth generation challenge, p.5-10, January 1984
	Peter van Beek , Rina Dechter, On the minimality and global consistency of row-convex constraint networks, Journal of the ACM (JACM), v.42 n.3, p.543-561, May 1995
	Barbara M. Smith, Constructing an asymptotic phase transition in random binary constraint satisfaction problems, Theoretical Computer Science, v.265 n.1_2, p.265-283, 08/28/2001
	Fedor V. Fomin , Dimitrios M. Thilikos, On the monotonicity of games generated by symmetric submodular functions, Discrete Applied Mathematics, v.131 n.2, p.323-335, 12 September 2003
	Fabrizio d'Amore , Fabio Iacobini, On-line algorithms for networks of temporal constraints, Journal of Discrete Algorithms, v.1 n.3-4, p.303-312, June 2003
	I. Miguel , Q. Shen, Solution Techniques for Constraint Satisfaction Problems: Foundations, Artificial Intelligence Review, v.15 n.4, p.243-267, June 2001
	I. Miguel , Q. Shen, Solution Techniques for Constraint Satisfaction Problems: Advanced Approaches, Artificial Intelligence Review, v.15 n.4, p.269-293, June 2001
	W. Eric Grimson, On the Recognition of Curved Objects, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.6, p.632-643, June 1989
	I. Navarrete , A. Sattar , R. Wetprasit , R. Marin, On point-duration networks for temporal reasoning, Artificial Intelligence, v.140 n.1-2, p.39-70, September 2002
	Marco Gavanelli , Evelina Lamma , Paola Mello , Michela Milano, Dealing with incomplete knowledge on CLP(FD) variable domains, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.2, p.236-263, March 2005
	Frédéric Goualard , Laurent Granvilliers, Controlled propagation in continuous numerical constraint networks, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
	W. Eric L. Grimson, The Combinatorics of Heuristic Search Termination for Object Recognition in Cluttered Environments, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.9, p.920-935, September 1991
	David Cohen , Peter Jeavons , Richard Gault, New tractable constraint classes from old, Exploring artificial intelligence in the new millennium, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
	Andrei A. Bulatov, A dichotomy theorem for constraint satisfaction problems on a 3-element set, Journal of the ACM (JACM), v.53 n.1, p.66-120, January 2006
	Zdeněk Dvořák , Daniel Král , Ondřej Pangrác, Locally consistent constraint satisfaction problems, Theoretical Computer Science, v.348 n.2, p.187-206, 8 December 2005
	Alan Frieze , Michael Molloy, The satisfiability threshold for randomly generated binary constraint satisfaction problems, Random Structures & Algorithms, v.28 n.3, p.323-339, May 2006
	P. Félix , S. Barro , R. Marín, Fuzzy constraint networks for signal pattern recognition, Artificial Intelligence, v.148 n.1-2, p.103-140, August 2003
	P. Félix , S. Barro, A fuzzy model for the representation and recognition of linguistically described trends, Intelligent Data Analysis, v.5 n.6, p.503-529, December 2001
	Nalaka Gooneratne , Zahir Tari, Matching independent global constraints for composite web services, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China
	Javier Larrosa , Gabriel Valiente, Constraint satisfaction algorithms for graph pattern matching, Mathematical Structures in Computer Science, v.12 n.4, p.403-422, August 2002
	Mira Balaban , Dan Braha, Temporal reasoning in process planning, Artificial Intelligence for Engineering Design, Analysis and Manufacturing, v.13 n.2, p.91-104, April 1999
	Manuel Bodirsky , Martin Kutz, Determining the consistency of partial tree descriptions, Artificial Intelligence, v.171 n.2-3, p.185-196, February, 2007
	Martin Michalowski , Craig A. Knoblock , Ken Bayer , Berthe Y. Choueiry, Exploiting automatically inferred constraint-models for building identification in satellite imagery, Proceedings of the 15th annual ACM international symposium on Advances in geographic information systems, November 07-09, 2007, Seattle, Washington
	Montserrat Abril , Miguel A. Salido , Federico Barber, Distributed search in railway scheduling problems, Engineering Applications of Artificial Intelligence, v.21 n.5, p.744-755, August, 2008
	Christian Bessiere , Emmanuel Hebrard , Brahim Hnich , Toby Walsh, The Complexity of Reasoning with Global Constraints, Constraints, v.12 n.2, p.239-259, June 2007
	Rolf Backofen , Sebastian Will, A Constraint-Based Approach to Fast and Exact Structure Prediction in Three-Dimensional Protein Models, Constraints, v.11 n.1, p.5-30, January 2006
	Steven Woods , Qiang Yang, Program Understanding as Constraint Satisfaction: Representation and Reasoning Techniques, Automated Software Engineering, v.5 n.2, p.147-181, April 1998
	Luca Chittaro , Angelo Montanari, Temporal representation and reasoning in artificial intelligence: Issues and approaches, Annals of Mathematics and Artificial Intelligence, v.28 n.1-4, p.47-106, 2000
	Rattana Wetprasit , Abdul Sattar , Lina Khatib, Representation and Reasoning with Multi-Point Events, Constraints, v.5 n.3, p.211-249, July 2000
	James E. Borrett , Edward P. K. Tsang, A Context for Constraint Satisfaction Problem Formulation Selection, Constraints, v.6 n.4, p.299-327, October 2001
	Ian P. Gent , Ewan Macintyre , Patrick Prosser , Barbara M. Smith , Toby Walsh, Random Constraint Satisfaction: Flaws and Structure, Constraints, v.6 n.4, p.345-372, October 2001
	Christine Gaspin, RNA Secondary Structure Determination and Representation Based on Constraints Satisfaction, Constraints, v.6 n.2-3, p.201-221, June 2001
	S. Durga Bhavani , Arun K. Pujari, EvIA - Evidential Interval Algebra and Heuristic Backtrack-Free Algorithm, Constraints, v.9 n.3, p.193-218, July 2004
	Said Belhadji , Amar Isli, Temporal Constraint Satisfaction Techniques in Job ShopScheduling Problem Solving, Constraints, v.3 n.2-3, p.203-211, June 1998
	B. M. W. Cheng , K. M. F. Choi , J. H. M. Lee , J. C. K. Wu, Increasing Constraint Propagation by Redundant Modeling: \an Experience Report, Constraints, v.4 n.2, p.167-192, May 1999
	Hachemi Bennaceur, A Comparison between SAT and CSP Techniques, Constraints, v.9 n.2, p.123-138, April 2004
	Pascal Van Hentenryck , Vijay Saraswat, Constraint Programming: Strategic Directions, Constraints, v.2 n.1, p.7-33, April 1997
	Rina Dechter, Bucket Elimination: a Unifying Framework for ProcessingHard and Soft Constraints, Constraints, v.2 n.1, p.51-55, April 1997
	Lisa Purvis , Pearl Pu, COMPOSER: A case-based reasoning system for engineering design, Robotica, v.16 n.3, p.285-295, May 1998
	Ian Miguel , Qiang Shen, Hard, flexible and dynamic constraint satisfaction, The Knowledge Engineering Review, v.14 n.3, p.199-220, September 1999
	Massimiliano Caramia , Paolo Dell'olmo, Constraint Propagation in Graph Coloring, Journal of Heuristics, v.8 n.1, p.83-107, January 2002
	Dnyanesh G. Rajpathak , Enrico Motta , Zdenek Zdrahal , Rajkumar Roy, A Generic Library of Problem Solving Methods for Scheduling Applications, IEEE Transactions on Knowledge and Data Engineering, v.18 n.6, p.815-828, June 2006
	Christian Bessiere , Romuald Debruyne, Theoretical analysis of singleton arc consistency and its extensions, Artificial Intelligence, v.172 n.1, p.29-41, January, 2008
	C. W. Choi , J. H.M. Lee , P. J. Stuckey, Removing propagation redundant constraints in redundant modeling, ACM Transactions on Computational Logic (TOCL), v.8 n.4, p.23-es, August 2007
	Zineb Habbas , Michael Krajecki , Daniel Singer, Decomposition techniques for parallel resolution of constraint satisfaction problems in shared memory: a comparative study, International Journal of Computational Science and Engineering, v.1 n.2-4, p.192-206, May 2005
	Duc Nghia Pham , John Thornton , Abdul Sattar, Modelling and solving temporal reasoning as propositional satisfiability, Artificial Intelligence, v.172 n.15, p.1752-1782, October, 2008
	A. Otero , P. Félix , S. Barro, A fuzzy constraint satisfaction approach for signal abstraction, International Journal of Approximate Reasoning, v.50 n.2, p.324-340, February, 2009
	Meinolf Sellmann, Approximated consistency for the automatic recording constraint, Computers and Operations Research, v.36 n.8, p.2341-2347, August, 2009
	Kenil K. C. Cheng , Roland H. C. Yap, Search space reduction and Russian Doll search, Proceedings of the 22nd national conference on Artificial intelligence, p.179-184, July 22-26, 2007, Vancouver, British Columbia, Canada
	Hubie Chen, Collapsibility and consistency in quantified constraint satisfaction, Proceedings of the 19th national conference on Artifical intelligence, p.155-160, July 25-29, 2004, San Jose, California
	Yuanlin Zhang , Eugene C. Freuder, Tractable tree convex constraint networks, Proceedings of the 19th national conference on Artifical intelligence, p.197-202, July 25-29, 2004, San Jose, California
	Yuanlin Zhang , Roland H. C. Yap, Set intersection and consistency in constraint networks, Journal of Artificial Intelligence Research, v.27 n.1, p.441-464, September 2006
	Federico Barber, Reasoning on interval and point-based disjunctive metric constraints in temporal contexts, Journal of Artificial Intelligence Research, v.12 n.1, p.35-86, February 2000
	Romuald Debruyne , Christian Bessiére, Domain filtering consistencies, Journal of Artificial Intelligence Research, v.14 n.1, p.205-230, January 2001
	Mark S. Fox , Norman Sadeh , Can Baykan, Constrained heuristic search, Proceedings of the 11th international joint conference on Artificial intelligence, p.309-315, August 20-25, 1989, Detroit, Michigan
	C. Bessiere , E. Hebrard , B. Hnich , Z. Kiziltan , C.-G. Quimper , T. Walsh, The parameterized complexity of global constraints, Proceedings of the 23rd national conference on Artificial intelligence, p.235-240, July 13-17, 2008, Chicago, Illinois
	Rina Dechter , Judea Pearl, The anatomy of easy problems: a constraint-satisfaction formulation, Proceedings of the 9th international joint conference on Artificial intelligence, p.1066-1072, August 18-23, 1985, Los Angeles, California
	Eugene C. Freuder , Michael J. Quinn, Taking advantage of stable sets of variables in constraint satisfaction problems, Proceedings of the 9th international joint conference on Artificial intelligence, p.1076-1078, August 18-23, 1985, Los Angeles, California
	Hans Werner Guesgen, A universal programming language, Proceedings of the 11th international joint conference on Artificial intelligence, p.60-65, August 20-25, 1989, Detroit, Michigan
	Rina Dechter , Itay Meiri, Experimental evaluation of preprocessing techniques in constraint satisfaction problems, Proceedings of the 11th international joint conference on Artificial intelligence, p.271-277, August 20-25, 1989, Detroit, Michigan
	Peter van Beek , Dennis W. Manchak, The design and experimental analysis of algorithms for temporal reasoning, Journal of Artificial Intelligence Research, v.4 n.1, p.1-18, Jnauary 1996
	Peter Van Beek, Approximation algorithms for temporal reasoning, Proceedings of the 11th international joint conference on Artificial intelligence, p.1291-1296, August 20-25, 1989, Detroit, Michigan
	Patrick Prosser, Domain filtering can degrade intelligent backtracking search, Proceedings of the 13th international joint conference on Artifical intelligence, p.262-267, August 28-September 03, 1993, Chambery, France
	Roberto J. Bayardo , Daniel P. Miranker, On the space-time trade-off in solving constraint satisfaction problems, Proceedings of the 14th international joint conference on Artificial intelligence, p.558-562, August 20-25, 1995, Montreal, Quebec, Canada
	Georg Gottlob , Nicola Leone , Francesco Scarcello, A comparison of structural CSP decomposition methods, Proceedings of the 16th international joint conference on Artifical intelligence, p.394-399, July 31-August 06, 1999, Stockholm, Sweden
	Thomas Schiex , Helene Fargier , Gerard Verfaillie, Valued constraint satisfaction problems: hard and easy problems, Proceedings of the 14th international joint conference on Artificial intelligence, p.631-637, August 20-25, 1995, Montreal, Quebec, Canada
	Rina Dechter , Judea Pearl, Directed constraint networks: a relational framework for causal modeling, Proceedings of the 12th international joint conference on Artificial intelligence, p.1164-1170, August 24-30, 1991, Sydney, New South Wales, Australia
	Yuanlin Zhang , Roland H. C. Yap, Consistency and set intersection, Proceedings of the 18th international joint conference on Artificial intelligence, p.263-268, August 09-15, 2003, Acapulco, Mexico
	Zeev Collin , Rina Dechter , Shmuel Katz, On the feasibility of distributed constraint satisfaction, Proceedings of the 12th international joint conference on Artificial intelligence, p.318-324, August 24-30, 1991, Sydney, New South Wales, Australia
	Jean-François Baget , Yannic S. Tognetti, Backtracking through biconnected components of a constraint graph, Proceedings of the 17th international joint conference on Artificial intelligence, p.291-296, August 04-10, 2001, Seattle, WA, USA