ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR06-078 | 27th June 2006 00:00

Improving Deterministic and Randomized Exponential-Time Algorithms for the Satisfiability, the Colorability, and the Domatic Number Problem

RSS-Feed

Abstract:

NP-complete problems cannot have efficient algorithms unless P = NP. Due to their importance in practice, however, it is useful to improve the known exponential-time algorithms for NP-complete problems. We survey some of the recent results on such improved exponential-time algorithms for the NP-complete problems satisfiability, graph colorability, and the domatic number problem. The deterministic time bounds are compared with the corresponding time bounds of randomized algorithms, which often run faster but only at the cost of having a certain error probability.


Paper:

TR06-078 | 12th June 2006 00:00

Improving Deterministic and Randomized Exponential-Time Algorithms for the Satisfiability, the Colorability, and the Domatic Number Problem


Abstract:

NP-complete problems cannot have efficient algorithms unless P = NP. Due to their importance in practice, however, it is useful to improve the known exponential-time algorithms for NP-complete problems. We survey some of the recent results on such improved exponential-time algorithms for the NP-complete problems satisfiability, graph colorability, and the domatic number problem. The deterministic time bounds are compared with the corresponding time bounds of randomized algorithms, which often run faster but only at the cost of having a certain error probability.



ISSN 1433-8092 | Imprint