Worst-case time bounds for coloring and satisfiability problems

Bax, 1993, Inclusion and exclusion algorithm for the Hamiltonian path problem, Inform. Process. Lett., 47, 203, 10.1016/0020-0190(93)90033-6 Beigel, 1995, 3-Coloring in time O(1.3446n): a no-MIS algorithm, 444 D. Eppstein, Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction, in: Proceedings of the 12th Annual ACM–SIAM Symposium on Discrete Algorithms, pp. 329–337 Gurevich, 1987, Expected computation time for the Hamiltonian path problem, SIAM J. Comput., 16, 486, 10.1137/0216034 Held, 1962, A dynamic programming approach to sequencing problems, J. Soc. Indust. Appl. Math., 10, 196, 10.1137/0110015 Jian, 1986, An O(20.304n) algorithm for solving maximum independent set problem, IEEE Trans. Comput. C, 35, 847, 10.1109/TC.1986.1676847 Johnson, 1988, On generating all maximal independent sets, Inform. Process. Lett., 27, 119, 10.1016/0020-0190(88)90065-8 Kullman, 1996, Worst-case analysis, 3-SAT decision and lower bounds: Approaches to improved SAT algorithms Lawler, 1976, A note on the complexity of the chromatic number problem, Inform. Process. Lett., 5, 66, 10.1016/0020-0190(76)90065-X Monien, 1985, Solving satisfiability in less than 2n steps, Discrete Appl. Math., 10, 287, 10.1016/0166-218X(85)90050-2 Moon, 1965, On cliques in graphs, Israel J. Math., 3, 23, 10.1007/BF02760024 Paturi, 1997, Satisfiability coding lemma Paturi, 1998, An improved exponential-time algorithm for k-SAT, 628 Robson, 1986, Algorithms for maximum independent sets, J. Algorithms, 7, 425, 10.1016/0196-6774(86)90032-5 Shindo, 1990, A simple algorithm for finding a maximum clique and its worst-case time complexity, Systems Comput. Japan, 12, 1, 10.1002/scj.4690210301 Schiermeyer, 1993, Solving 3-satisfiability in less than 1.579n steps, 702, 379 Schiermeyer, 1994, Deciding 3-colorability in less than O(1.415n) steps, 177 Schiermeyer, 1996, Pure literal look ahead: An O(1.497) 3-satisfiability algorithm Schöning, 1999, A probabilistic algorithm for k-SAT and constraint satisfaction problems, 410 Tarjan, 1977, Finding a maximum independent set, SIAM J. Comput., 6, 537, 10.1137/0206038 Zhang, 1996, Number of models and satisfiability of sets of clauses, Theoret. Comput. Sci., 155, 277, 10.1016/0304-3975(95)00144-1