Cover Image
QR Code

Exact Exponential Algorithms.

The article discusses exact exponential algorithms, focusing on the results of research concerning Maximum 2-Satisfiability, Graph Coloring, and Hamiltonian Path problems as of March 2013. It emphasizes potential surprises in research related to computing and presents unsolved problems relating to t...

Full description

Published in:Communications of the ACM Vol. 56; no. 3; pp. 80 - 89
Main Authors: FOMIN, FEDOR V., KASKI, PETTERI
Format: Article
Published: Association for Computing Machinery Mar2013
Subjects:
Exponential functions
Algorithm research
Problem solving
Parameter estimation
Approximation algorithms
Computer science research
Online Access:View this record in EBSCOhost
Summary:The article discusses exact exponential algorithms, focusing on the results of research concerning Maximum 2-Satisfiability, Graph Coloring, and Hamiltonian Path problems as of March 2013. It emphasizes potential surprises in research related to computing and presents unsolved problems relating to topics such as edge coloring. Topics include the use of parameterized algorithms and approximation algorithms in circumstances involving intractability, the improvement of exhaustive search, and dynamic computing.