From SAT to Maximum Independent Set: A New Approach to Characterize Tractable Classes.
Yazid BoumarafiLakhdar SaisYakoub SalhiPublished in: LPAR (2017)
Keyphrases
- tractable classes
- maximum independent set
- constraint satisfaction problems
- reasoning problems
- graph theory
- independent set
- graph theoretic
- path consistency
- structural properties
- temporal reasoning
- bounded treewidth
- constraint satisfaction
- temporal constraints
- search space
- decision procedures
- constraint propagation
- tree decomposition
- constraint networks
- sat solvers
- variable elimination
- social network analysis
- np complete
- knowledge representation