An Efficient Heuristic for SAT Exploiting Connected Components of the Problem

Abstract

This paper describes a new variable ordering heuristic for a Boolean satisfiability problem (SAT) solver based on search by the method DPLL. The basic idea of the heuristic is to derive a dynamic graph from the state of the problem during search.

Keywords

• Efficient
• Heuristic
• Exploiting
• Connected
• Components
• Problem