Parallel Algorithms for Refutation Tree Problem on Formal Graph Systems

Tomoyuki UCHIDA  Takayoshi SHOUDAI  Satoru MIYANO  

IEICE TRANSACTIONS on Information and Systems   Vol.E78-D   No.2   pp.99-112
Publication Date: 1995/02/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity
algorithm and computational complexity,  formal graph system,  refutation tree,  two-terminal series parallel graph,  outerplanar graph,  

Full Text: PDF(1MB)>>
Buy this Article

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 O(log2nlogm) time with O(nm) processors on an EREW PRAM. For the FGS defining outerplanar graphs, we show that the refutation tree problem can be solved in O(log2n) time with O(nm) processors on an EREW PRAM. Here, n and m are the numbers of vertices and edges of an input graph, respectively.