An algebraic theory of graph reduction
An algebraic theory of graph reduction
复制标题
图简化的代数理论
DOI：
--
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
D. Seese
中科院分区：
文献类型：
--
作者：
S. Arnborg;B. Courcelle;A. Proskurowski;D. Seese
我们展示了如何在一元二阶逻辑和有界树宽可定义的图形类的成员资格可以决定有限的终止减少规则集。该方法是建设性的意义上说，我们描述了一个算法，将产生，从一元二阶逻辑公式和整数k，使得由公式定义的类是树宽≤ k，一组重写规则，减少任何成员的类的许多图之一，在一些步骤的大小的图形。这个归约系统对应于在图的大小中时间线性地运行的算法。
We show how membership in classes of graphs definable in monadic second order logic and of bounded treewidth can be decided by finite sets of terminating reduction rules. The method is constructive in the sense that we describe an algorithm which will produce, from a formula in monadic second order logic and an integer k such that the class defined by the formula is of treewidth ≤ k, a set of rewrite rules that reduces any member of the class to one of finitely many graphs, in a number of steps bounded by the size of the graph. This reduction system corresponds to an algorithm that runs in time linear in the size of the graph.