Enumerating Potential Maximal Cliques via SAT and ASP
Enumerating Potential Maximal Cliques via SAT and ASP
复制标题
通过 SAT 和 ASP 枚举潜在的最大派系
DOI：
10.24963/ijcai.2019/156
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Matti Järvisalo
中科院分区：
文献类型：
--
作者：
T. Korhonen;Jeremias Berg;Matti Järvisalo
Bouchitté-Todinca算法（BT）在所谓的潜在最大团（PMCs）上运行动态规划，产生了一种实际有效的树宽和广义超树宽方法。在实践中，PMC的枚举是BT的可扩展性瓶颈。我们建议使用声明式求解器PMC枚举作为替代的专门PMC枚举算法在当前的BT实现。提出了基于布尔可满足性（SAT）和回答集编程（ASP）的PMC枚举方法，为提高BT的效率开辟了新的可能性。
The Bouchitté-Todinca algorithm (BT), operating dynamic programming over the so-called potential maximal cliques (PMCs), yields a practically efficient approach to treewidth and generalized hypertreewidth. The enumeration of PMCs is a scalability bottleneck for BT in practice. We propose the use of declarative solvers for PMC enumeration as a substitute for the specialized PMC enumeration algorithms employed in current BT implementations. The presented Boolean satisfiability (SAT) and answer set programming (ASP) based PMC enumeration approaches open up new possibilities for improving the efficiency of BT in practice.
影响因子：
1
作者：
Tamaki, Hisao
通讯作者：
Tamaki, Hisao