Directors:
John Franco and
John Schlipf
Sponsor:
Office of Naval Research
Research:
The research work of this laboratory centers on structural and
algorithmic properties of NP-complete problems related to logic. In
particular, problems such as propositional satisfiability, are studied
with the goal of finding good approximation algorithms and efficiently
solvable classes of instances. We study the relationship among
graph/matrix theoretic problems, optimization problems, and logic
problems with the intention of developing and exploiting tools in one
domain to solve problems in another domain. For more information
please write to me at
franco@gauss.cs.uc.edu