Review of exact exponential algorithms by Fedor V. Fomin and Dieter Kratsch
Index Terms
- Review of exact exponential algorithms by Fedor V. Fomin and Dieter Kratsch
Recommendations
Nontriviality for exponential time w.r.t. weak reducibilities
A set A is nontrivial for the linear exponential time class E=DTIME(2^l^i^n) if A@?E and the sets from E which can be reduced to A are not from a single level DTIME(2^k^n) of the linear exponential hierarchy. Similarly, a set A is nontrivial for the ...
Parameterized and Exact-Exponential Algorithms for the Read-Once Integer Refutation Problem in UTVPI Constraints
Combinatorial Optimization and ApplicationsAbstractIn this paper, we discuss parameterized and exact-exponential algorithms for the read-once integer refutability problem in Unit Two Variable Per Inequality (UTVPI) constraint systems. UTVPI constraint systems (UCSs) arise in a number of domains ...
Nontriviality for exponential time w.r.t weak reducibilities
TAMC'10: Proceedings of the 7th annual conference on Theory and Applications of Models of ComputationA set A is nontrivial for the linear exponential time class E=DTIME(2lin) if A∈E and the sets from E which can be reduced to A are not from a single level DTIME(2kn) of the linear exponential hierarchy Similarly, a set A is nontrivial for the polynomial ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Check for updates
Qualifiers
- Review-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 94Total Downloads
- Downloads (Last 12 months)2
- Downloads (Last 6 weeks)0
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in