Exact exponential algorithms

By Fedor V. Fomin, Petteri Kaski. CACM, 2010

543 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/124c0e88b5739ec390f2bf8ed1c4ebf528d5eded

Citations in the corpus

• Lower bounds based on the Exponential Time Hypothesis (2011, unknown): “A variant of ETH, called the Strong Exponential Time Hypothesis (SETH) can be used to give even more refined lower bounds saying, e.g., that a parameterized problem cannot be solved in time (2 ")knO(1) for any " > 1.”