子图同构（SI）问题是一项计算任务，其中给出了两个图G和H作为输入，并且一个人必须确定G是否包含与H同构的子图。
这是一个NP完全问题。
我想知道它与SAT问题的关系。我特别希望这个问题可以在整个SAT解算器中解决（例如miniSAT）。我需要一个可以在多项式时间内完成从SI到SAT问题的映射的算法，然后可以使用SAT分配从节点查找映射G到H的节点。
任何想法 ？？？
甲SAT对于编码图同构问题在描述SAT 2013的论文“在图形非同构的分辨率复杂性”。
SAT
Minisat是最著名的SAT解算器之一，但它具有多个后继者，这些后继者可能更快且成功率更高。尝试使用Cryptominisat（版本2.9.5似乎比版本3快；它支持并行线程），Riss3g或Clasp。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
点击生成二维码
我来说两句