×

Experimental evaluation of preprocessing algorithms for constraint satisfaction problems. (English) Zbl 0942.68576


MSC:

68Q25 Analysis of algorithms and problem complexity
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Arnborg, S; Corneil, D.G; Proskurowski, A, Complexity of finding embeddings in a k-tree, SIAM J. algebraic discrete methods, 8, 2, 177-184, (1987)
[2] Collin, Z; Decher, R; Katz, S, On the feasibility of distributed constraint satisfaction, (), 318-324 · Zbl 0747.68065
[3] Dechter, R, Enhancement schemes for constraint processing: backjumping, learning, and cutset decomposition, Artif. intell., 41, 3, 273-312, (1990)
[4] Dechter, R, Constraint networks, (), 276-285
[5] Dechter, R; Kask, K, Combining GSAT and path consistency for solving constraint satisfaction problems, 94-17, (1994), Information and Computer Science Department, University of California Irvine, CA
[6] Dechter, R; Pearl, J, Network-based heuristics for constraint-satisfaction problems, Artif. intell., 34, 1, 1-38, (1987) · Zbl 0643.68156
[7] Dechter, R; Pearl, J, Tree clustering for constraint networks, Artif. intell., 38, 353-366, (1989) · Zbl 0665.68084
[8] Even, S, ()
[9] Freuder, E.C, Synthesizing constraint expression, Commun. ACM, 21, 11, 958-965, (1978) · Zbl 0386.68065
[10] Freuder, E.C, A sufficient condition for backtrack-free search, J. ACM, 29, 1, 24-32, (1982) · Zbl 0477.68063
[11] Frost, D; Dechter, R, Dead-end driven learning, ()
[12] Gaschnig, J, Performance measurement and analysis of certain search algorithms, ()
[13] Ginsberg, M, Search lesson learned from crossword puzzles, (), 210-215
[14] Haralick, R.M; Elliott, G.L, Increasing tree-search efficiency for constraint satisfaction problems, Artif. intell., 14, 3, 263-313, (1980)
[15] Mackworth, A.K, Constraint satisfaction, (), 285-293
[16] Mackworth, A.K, Consistency in networks of relations, Artif. intell., 8, 1, 99-118, (1977) · Zbl 0341.68061
[17] Mitchell, D; Selman, B; Levesque, H.J, Hard and easy distributions of SAT problems, (), 459-465
[18] Montanari, U, Networks of constraints: fundamental properties and applications to picture processing, Inf. sci., 7, 2, 95-132, (1974) · Zbl 0284.68074
[19] Nudel, B, Consistent-labeling problems and their algorithms: expected-complexities and theory-based heuristics, Artif. intell., 21, 1-2, 135-178, (1983)
[20] Prosser, P, Hybrid algorithms for the constraint satisfaction problem, Comput. intell., 9, 3, 268-299, (1993)
[21] Purdom, P, Search rearrangement backtracking and polynomial average time, Artif. intell., 21, 1-2, 117-133, (1983)
[22] Purdom, P.W; Robertson, E.L; Brown, C.A, Backtracking with multi-level dynamic search rearrangement, Acta. inf., 15, 2, 99-114, (1981) · Zbl 0431.68066
[23] Rosiers, W; Bruynooghe, M, Empirical study of some constraint satisfaction algorithms, ()
[24] Sadeh, N; Fox, M, Variable and value ordering heuristics for hard constraint satisfaction problems: an application to job shop scheduling, ()
[25] Stallman, R.M; Sussman, G.J, Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis, Artif. intell., 9, 2, 135-196, (1977) · Zbl 0372.94024
[26] Stone, H.S; Stone, J.M, Efficient search techniques—an empirical study of the N-queens problem, ()
[27] Van Hentenryck, P; Dincbas, M, Forward checking in logic programming, (), 229-255
[28] Waltz, D, Understanding line drawings of scenes with shadows, ()
[29] Zabih, R; McAllester, D, A rearrangement search strategy for determining propositional satisfiability, (), 155-160
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.