ECCC-Report TR06-078https://eccc.weizmann.ac.il/report/2006/078Comments and Revisions published for TR06-078en-usTue, 27 Jun 2006 00:00:00 +0300
Revision 1
| Improving Deterministic and Randomized Exponential-Time Algorithms for the Satisfiability, the Colorability, and the Domatic Number Problem |
Tobias Riege,
Jörg Rothe
https://eccc.weizmann.ac.il/report/2006/078#revision1NP-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.
Tue, 27 Jun 2006 00:00:00 +0300https://eccc.weizmann.ac.il/report/2006/078#revision1
Paper TR06-078
| Improving Deterministic and Randomized Exponential-Time Algorithms for the Satisfiability, the Colorability, and the Domatic Number Problem |
Tobias Riege,
Jörg Rothe
https://eccc.weizmann.ac.il/report/2006/078NP-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.
Wed, 21 Jun 2006 19:51:17 +0300https://eccc.weizmann.ac.il/report/2006/078