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

Простая страница элемента
dc.creatorRiege,Tobias
dc.creatorRothe,Jörg
dc.date2006
dc.date.accessioned2024-02-06T12:54:25Z
dc.date.available2024-02-06T12:54:25Z
dc.descriptionNP-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.
dc.formattext/html
dc.identifierhttps://doi.org/10.3217/jucs-012-06-0725
dc.identifierhttps://lib.jucs.org/article/28628/
dc.identifier.urihttps://openrepository.mephi.ru/handle/123456789/9041
dc.languageen
dc.publisherJournal of Universal Computer Science
dc.relationinfo:eu-repo/semantics/altIdentifier/eissn/0948-6968
dc.relationinfo:eu-repo/semantics/altIdentifier/pissn/0948-695X
dc.rightsinfo:eu-repo/semantics/openAccess
dc.rightsJ.UCS License
dc.sourceJUCS - Journal of Universal Computer Science 12(6): 725-745
dc.subjectexact computation
dc.subjectexponential-time algorithms
dc.subjectdeterministic algorithms
dc.subjectrandomized algorithms
dc.titleImproving Deterministic and Randomized Exponential-Time Algorithms for the Satisfiability, the Colorability, and the Domatic Number Problem
dc.typeResearch Article
Файлы
Коллекции