Accelerating backtrack search with a best-first-search strategy

Appel, A.W. and George, L. (1996). Register interference graphs, http://www.cs.princeton.edu/ ~appel/graphdata/.Search in Google Scholar

Bender, E.A. and Wilf, H.S. (1985). A theoretical analysis of backtracking in the graph coloring problem, Journal of Algorithms 6(2): 275-282.10.1016/0196-6774(85)90044-6Search in Google Scholar

Biere, A. (2008). Adaptive restart strategies for conflict driven SAT solvers, in H. Kleine Büning and X. Zhao (Eds.), Theory and Applications of Satisfiability Testing-SAT 2008, Springer, Berlin, pp. 28-33.10.1007/978-3-540-79719-7_4Search in Google Scholar

Brélaz, D. (1979). New methods to color the vertices of a graph, Communications of the ACM 22(4): 251-256.10.1145/359094.359101Search in Google Scholar

Brown, C.A., Finkelstein, L. and Purdom, P.W.J. (1996). Backtrack searching in the presence of symmetry, Nordic Journal of Computing 3(3): 203-219.Search in Google Scholar

Brown, J.R. (1972). Chromatic scheduling and the chromatic number problem, Management Science 19(4): 456-463.10.1287/mnsc.19.4.456Search in Google Scholar

Cheeseman, P., Kanefsky, B. and Taylor, W.M. (1991). Where the really hard problems are, 12th International Joint Conference on Artificial Intelligence (IJCAI ’91), Sydney, Australia, pp. 331-337.Search in Google Scholar

Davis, M., Logemann, G. and Loveland, D. (1962). A machine program for theorem proving, Communications of the ACM 5(7): 394-397.10.1145/368273.368557Search in Google Scholar

Davis, M. and Putnam, H. (1960). A computing procedure for quantification theory, Journal of the ACM 7(3): 201-215.10.1145/321033.321034Search in Google Scholar

Dechter, R. (1990). Enhancement schemes for constraint processing: Backjumping, learning and cutset decomposition, Artificial Intelligence 41(3): 273-312.10.1016/0004-3702(90)90046-3Search in Google Scholar

Dechter, R. (2003). Constraint Processing, Morgan Kaufmann, San Francisco, CA.Search in Google Scholar

Dechter, R. and Frost, D. (2002). Backjump-based backtracking for constraint satisfaction problems, Artificial Intelligence 136(2): 147-188.10.1016/S0004-3702(02)00120-0Search in Google Scholar

Eén, N. and Sörensson, N. (2004). An extensible SAT-solver, in E. Giunchiglia and A. Tacchella (Eds.), Theory and Applications of Satisfiability Testing, Lecture Notes in Computer Science, Vol. 2919, Springer, Berlin/Heidelberg, pp. 502-518.10.1007/978-3-540-24605-3_37Search in Google Scholar

Geelen, P.A. (1992). Dual viewpoint heuristics for binary constraint satisfaction problems, Proceedings of the 10th European Conference on Artificial Intelligence, Vienna, Austria, pp. 31-35.Search in Google Scholar

Gomes, C.P., Selman, B., Crato, N. and Kautz, H. (2000). Heavy-tailed phenomena in satisfiability and constraint satisfaction problems, Journal of Automated Reasoning 24(1-2): 67-100.10.1023/A:1006314320276Search in Google Scholar

Gomes, C., Selman, B. and Kautz, H. (1998). Boosting combinatorial search through randomization, Proceedings of the Fifteenth National Conference on Artificial Intelligence (AAAI-98), Madison, WI, USA, pp. 431-437.Search in Google Scholar

Haim, S. and Heule, M. (2010). Towards ultra rapid restarts, Technical report, UNSW/TU Delft, Sydney/Delft.Search in Google Scholar

Hogg, T. and Williams, C.P. (1994). The hardest constraint problems: A double phase transition, Artificial Intelligence 69(1-2): 359-377.10.1016/0004-3702(94)90088-4Search in Google Scholar

Hutter, F., Hamadi, Y., Hoos, H. and Leyton-Brown, K. (2006). Performance prediction and automated tuning of randomized and parametric algorithms, in F. Benhamou (Ed.), Principles and Practice of Constraint Programming-CP 2006, Springer, Berlin/Heidelberg, pp. 213-228.10.1007/11889205_17Search in Google Scholar

Jia, H. and Moore, C. (2004). How much backtracking does it take to color random graphs? Rigorous results on heavy tails, Principles and Practice of Constraint Programming (CP 2004), Toronto, Canada, pp. 742-746.Search in Google Scholar

Kautz, H., Horvitz, E., Ruan, Y., Gomes, C. and Selman, B. (2002). Dynamic restart policies, 18th National Conference on Artificial Intelligence, Edmonton, Canada, pp. 674-681.Search in Google Scholar

Knuth, D.E. (1975). Estimating the efficiency of backtrack programs, Mathematics of Computation 29(129): 121-139.10.2307/2005469Search in Google Scholar

Luby, M., Sinclair, A. and Zuckerman, D. (1993). Optimal speedup of Las Vegas algorithms, Information Processing Letters 47(4): 173-180.10.1016/0020-0190(93)90029-9Search in Google Scholar

Mann, Z. (2011). Optimization in Computer Engineering- Theory and Applications, Scientific Research Publishing, Irvine, CA.Search in Google Scholar

Mann, Z. and Szajkó, A. (2012). Complexity of different ILP models of the frequency assignment problem, in Z. Mann (Ed.), Linear Programming-New Frontiers in Theory and Applications, Nova Science Publishers, New York, NY, pp. 305-326.Search in Google Scholar

Mann, Z. and Szajkó, A. (2010a). Determining the expected runtime of exact graph coloring, Proceedings of the 13th International Multiconference on Information Society-IS 2010, Ljubljana, Slovenia, Vol. A, pp. 389-393.Search in Google Scholar

Mann, Z. and Szajkó, A. (2010b). Improved bounds on the complexity of graph coloring, Proceedings of the 12th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, Timisoara, Romania, pp. 347-354.10.1109/SYNASC.2010.61Search in Google Scholar

Mann, Z. and Szép, T. (2010). BCAT: A framework for analyzing the complexity of algorithms, 8th IEEE International Symposium on Intelligent Systems and Informatics, Subotica, Serbia, pp. 297-302.Search in Google Scholar

Moskewicz, M.W., Madigan, C.F., Zhao, Y., Zhang, L. and Malik, S. (2001). Chaff: Engineering an efficient SAT solver, Proceedings of the 38th Annual Design Automation Conference, Las Vegas, NV, USA, pp. 530-535.Search in Google Scholar

Russell, S.J. and Norvig, P. (2010). Artificial Intelligence: A Modern Approach, 3rd Edn., Prentice Hall, Upper Saddle River, NJ. Schaefer, R., Byrski, A., Kołodziej, J. and Smołka, M. (2012). An agent-based model of hierarchic genetic search, Computers and Mathematics with Applications 64(12): 3763-3776.Search in Google Scholar

Trick, M. (2003). COLOR03 graph coloring benchmarks, http://mat.gsia.cmu.edu/COLOR03/.Search in Google Scholar

Walsh, T. (1999). Search in a small world, Proceedings of the 16th International Joint Conference on Artificial Intelligence, Stockholm, Sweden, pp. 1172-1177.Search in Google Scholar

Wilf, H.S. (1984). Backtrack: An O(1) expected time algorithm for the graph coloring problem, Information Processing Letters 18(3): 119-121.10.1016/0020-0190(84)90013-9Search in Google Scholar

Wu, H. and van Beek, P. (2003). Restart strategies: Analysis and simulation, Principles and Practice of Constraint Programming-CP 2003, Kinsale, Ireland, p. 1001. Search in Google Scholar