3-coloring in time $O(1.3446^n)$: a no-MIS algorithm

Richard Beigel and David Eppstein
Tech. report TR95-033, Electronic Colloq. on Computational Complexity, 1995
Proc. 36th Symp. Foundations of Computer Science, IEEE, Oct 1995, pp. 444–453
ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/1995/TR95-033/index.html

Cited by:

• Molecular computing, bounded nondeterminism, and efficient recursion
• Biomolecular computing—a shape of computation to come
• DNA models and algorithms for NP-complete problems
• On limited versus polynomial nondeterminism
• Volume Bounded Molecular Computation
• Which problems have strongly exponential complexity?
• Vertex cover: further observations and further improvements
• Circuit evaluation: thoughts on a killer application in DNA computing
• Executing parallel logical operations with DNA
• An efficient exact algorithm for constraint bipartite vertex cover
• A new approach on solving 3-satisfiability
• New upper bounds for maximum satisfiability
• New methods for 3-SAT decision and worst-case analysis
• A probabilistic algorithm for $k$-SAT and constraint satisfaction problems
• Upper bounds for MaxSat: Further improved
• Algorithms for SAT and upper bounds on their complexity
• Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics
• An algorithm for counting maximum weighted independent sets and its applications
• Three-colourability and forbidden subgraphs, II: Polynomial algorithms
• Frozen development in graph coloring
• On the complexity of $k$-SAT
• Exact algorithms for NP-hard problems: A survey
• Colouring random graphs in expected polynomial time
• Worst-case time bounds for coloring and satisfiability problems
• 3-SAT $\in RTIME(O(1.32793^n))$: Improving randomized local search by initializing strings of 3-clauses
• The resolution complexity of random graph $k$-colorability
• Generation and Comparison of Constraint-Based Heuristics Using the Structure of Constraints
• Worst-case analysis, 3-SAT decision and lower bounds: approaches for improved SAT algorithms
• The unreasonable effectiveness of alternation-based satisfiability algorithms
• The Resolution Complexity of Constraint Satisfaction
• Circuits, CNFs, and Satisfiability