Parallel Algorithms for Refutation Tree Problem on Formal Graph Systems
Parallel Algorithms for Refutation Tree Problem on Formal Graph Systems
复制标题
形式图系统上反驳树问题的并行算法
DOI：
--
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
S. Miyano
中科院分区：
文献类型：
--
作者：
Tomoyuki Uchida;Takayoshi Shoudai;S. Miyano
我们定义了一个用于重写图的新框架，称为形式图系统（FGS），它是一个具有超图而不是一阶逻辑中的术语的逻辑程序。我们首先证明一类图是由超边替换语法生成的，当且仅当它是由称为常规 FGS 的特殊形式的 FGS 定义的。与逻辑程序一样，我们可以为 FGS 定义反驳树。 TTSP 图和外平面图的类别可由常规 FGS 定义。然后，我们考虑为这些 FGS 构建图的反驳树的问题。对于定义 TTSP 图的 FGS，我们提出了一种在 EREW PRAM 上使用 O(n + m) 个处理器的 0(log2 n + log m) 时间的反驳树算法。对于定义外平面图的 FGS，我们表明反驳树问题可以在 EREW PRAM 上使用 O(n + rn ) 处理器在 0(log2 n) 时间内解决。这里，n和m分别是输入图的顶点和边的数量。
We define a new framework for rewriting graphs, called a formal graph system (FGS), which is a logic program having hypergraphs instead of terms in first-order logic. We first prove that a class of graphs is generated by a hyperedge replacement grammar if and only if it is defined by an FGS of a special form called a regular FGS. In the same way as logic programs, we can define a refutation tree for an FGS. The classes of TTSP graphs and outerplanar graphs are definable by regular FGSs. Then, we consider the problem of constructing a refutation tree of a graph for these FGSs. For the FGS defining TTSP graphs, we present a refutation tree algorithm of 0(log2 n + log m) time with O(n + m) processors on an EREW PRAM. For the FGS defining outerplanar graphs, we show that the refutation tree problem can be solved in 0(log2 n) time with O(n + rn ) processors on an EREW PRAM. Here, n and m are the numbers of vertices and edges of an input graph, respectively.