Parameterized algorithms for propositional satisfiability

Photograph of Stefan Szeider

Stefan Szeider

(Durham)

In the talk we will consider several parameterizations of the propositional satisfiability problem (SAT) that give rise to efficient parameterized algorithms. Parameterized algorithms provide a means for coping with computationally hard problems by guaranteeing worst-case time complexities which are exponential in terms of the parameter but uniformly polynomial in the size of the instance. In particular we will consider parameters that bound the acyclicity or the matching deficiency of graph representations of SAT instances and parameters that bound the distance of SAT instances from being Horn or bijunctive.
Tuesday 15th February 2005, 14:00
Robert Recorde Room
Department of Computer Science