论文标题
计算ASP和DATALOG中的H分区
Computing H-Partitions in ASP and Datalog
论文作者
论文摘要
有限的无向图$ g $的$ h $ - 分区是$ g $的顶点的标签，因此满足了模型图$ h $表示的约束。对于每个型号图$ h $，可以在非确定性多项式时间中确定是否给定输入图$ G $允许$ H $ - 分区。此外，Dantas等人已经显示了它。对于大多数模型图，此决策问题是确定性的多项式时间。在本文中，我们表明这些用于查找$ h $ - 分区的多项式时间算法可以在datalog中以分层的否定表示。此外，使用答案集求解器克林戈，我们进行了实验，以将直接的猜测和检查程序与Datalog程序进行比较。我们的实验表明，在克林戈中，猜测和检查程序的运行速度比其等效数据编写程序更快。
A $H$-partition of a finite undirected simple graph $G$ is a labeling of $G$'s vertices such that the constraints expressed by the model graph $H$ are satisfied. For every model graph $H$, it can be decided in non-deterministic polynomial time whether a given input graph $G$ admits a $H$-partition. Moreover, it has been shown by Dantas et al. that for most model graphs, this decision problem is in deterministic polynomial time. In this paper, we show that these polynomial-time algorithms for finding $H$-partitions can be expressed in Datalog with stratified negation. Moreover, using the answer set solver Clingo, we have conducted experiments to compare straightforward guess-and-check programs with Datalog programs. Our experiments indicate that in Clingo, guess-and-check programs run faster than their equivalent Datalog programs.
