Search
 
loader loading subjects...
cover
On the Modularity of Industrial SAT Instances
Carlos Ansótegui, Jordi Levy
11 - 20
10.3233/978-1-60750-842-7-11
Frontiers in Artificial Intelligence and Applications
Volume 232: Artificial Intelligence Research and Development
Abstract

Learning, re-starting and other techniques of modern SAT solvers have been shown efficient when solving SAT instances from industrial application. The ability to exploit the structure of these instances has been proposed as the responsible of such success. Here we study the modularity of some of these instances, used in the latest SAT competitions. Using a simple label propagation algorithm we show that the community structure of most of these SAT instances can be identified very efficiently. We also discuss how this structure may be used to speed up SAT solvers.

$35.00 / €27.50 / £22.00
Add PDF to cart