论文标题
图形的加权平板系统：评估复杂性
Weighted Tiling Systems for Graphs: Evaluation Complexity
论文作者
论文摘要
我们考虑加权的瓷砖系统来表示从图表到通勤半程的函数，例如自然半段或热带半度。该系统通过其状态标记图形的节点，并检查每个节点的邻域是否属于一组允许的瓷砖，并相应地分配权重。标签的重量是分配给节点的权重的半级产品，图形的重量是标记重量的半尿布。我们表明，我们可以使用这种形式主义对有趣的算法问题进行建模 - 例如计算图的集团数量或计算矩阵的永久性。评估问题是一个加权平板系统和图形，以计算图形的重量。我们研究评估问题的复杂性，并为几个交换性半节目提供紧密的上和下限。此外，如果输入图具有有限的树宽度，我们提供有效的评估算法。
We consider weighted tiling systems to represent functions from graphs to a commutative semiring such as the Natural semiring or the Tropical semiring. The system labels the nodes of a graph by its states, and checks if the neighbourhood of every node belongs to a set of permissible tiles, and assigns a weight accordingly. The weight of a labeling is the semiring-product of the weights assigned to the nodes, and the weight of the graph is the semiring-sum of the weights of labelings. We show that we can model interesting algorithmic questions using this formalism - like computing the clique number of a graph or computing the permanent of a matrix. The evaluation problem is, given a weighted tiling system and a graph, to compute the weight of the graph. We study the complexity of the evaluation problem and give tight upper and lower bounds for several commutative semirings. Further we provide an efficient evaluation algorithm if the input graph is of bounded tree-width.
