For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Parallel Algorithms for Refutation Tree Problem on Formal Graph Systems
Tomoyuki UCHIDA Takayoshi SHOUDAI Satoru MIYANO
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1995/02/25
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>>
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.