Name
Abstract | ||
|---|---|---|
The field of exact exponential time algorithms for NP-hard problems has thrived over the last decade. While exhaustive search remains asymptotically the fastest known algorithm for some basic problems, difficult and non-trivial exponential time algorithms have been found for a myriad of problems, including Graph Coloring, Hamiltonian Path, Dominating Set and 3-CNF-Sat. In some instances, improving these algorithms further seems to be out of reach. The CNF-Sat problem is the canonical example of a problem for which the trivial exhaustive search algorithm runs in time O(2^n), where n is the number of variables in the input formula. While there exist non-trivial algorithms for CNF-Sat that run in time o(2^n), no algorithm was able to improve the growth rate 2 to a smaller constant, and hence it is natural to conjecture that 2 is the optimal growth rate. The strong exponential time hypothesis (SETH) by Impagliazzo and Paturi [JCSS 2001] goes a little bit further and asserts that, for every epsilon |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1145/2925416 | ACM Trans. Algorithms |
Keywords | Field | DocType |
fastest known algorithm,non-trivial exponential time algorithm,basic problem,trivial exhaustive search algorithm,non-trivial algorithm,exact exponential time algorithm,cnf-sat problem,time o,strong exponential time hypothesis,np-hard problem,computational complexity,force,subset sum,set cover,algorithm design and analysis,hamiltonian path,set theory,np hard problems,graph theory,graph coloring,steiner trees,dominating set | Discrete mathematics,Approximation algorithm,Dominating set,Combinatorics,Hamiltonian path,Vertex cover,Time complexity,Mathematics,Exponential time hypothesis,Graph coloring,Computational complexity theory | Conference |
Volume | Issue | ISSN |
12 | 3 | 1549-6325 |
Citations | PageRank | References |
29 | 1.00 | 25 |
Authors | ||
9 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marek Cygan | 1 | 556 | 40.52 |
| Holger Dell | 2 | 220 | 16.74 |
| Daniel Lokshtanov | 3 | 1438 | 110.05 |
| Dániel Marx | 4 | 1952 | 113.07 |
| Jesper Nederlof | 5 | 294 | 24.22 |
| Yoshio Okamoto | 6 | 79 | 6.59 |
| Ramamohan Paturi | 7 | 1260 | 92.20 |
| Saket Saurabh | 8 | 2023 | 179.50 |
| Magnus Wahlström | 9 | 401 | 33.04 |