Paper Info
Title
Exact algorithms and complexity
Abstract
Over the past couple of decades, a series of exact exponential-time algorithms have been developed with improved run times for a number of problems including IndependentSet, k-SAT, and k-colorability using a variety of algorithmic techniques such as backtracking, dynamic programming, and inclusion-exclusion. The series of improvements are typically in the form of better exponents compared to exhaustive search. These improvements prompt several questions, chief among them is whether we can expect continued improvements in the exponent. Is there a limit beyond which one should not expect improvement? If we assume NP ≠ P or other appropriate complexity statement, what can we say about the likely exact complexities of various NP-complete problems?
Year
DOI
Venue
2010
10.1007/978-3-642-14186-7_2
SAT
Keywords
Field
DocType
exhaustive search,continued improvement,improved run time,better exponent,appropriate complexity statement,likely exact complexity,dynamic programming,exact exponential-time algorithm,exact algorithm,algorithmic technique,past couple,np complete problem
Dynamic programming,Combinatorics,Exponent,Brute-force search,Computer science,Algorithm,Backtracking
Conference
Volume
ISSN
ISBN
6175
0302-9743
3-642-14185-4
Citations 
PageRank 
References 
0
0.34
1
Authors
1
Name
Order
Citations
PageRank
Ramamohan Paturi1126092.20