## ＜テクニカルレポート＞Parallel Algorithms for Refutation Tree Problem on Formal Graph Systems

作成者 作成者名 所属機関 所属機関名 Department of Information Systems Kyushu University 九州大学大学院総合理工学研究科情報システム学専攻 著者識別子 作成者名 所属機関 所属機関名 Faculty of Engineering, Yamaguchi University 山口大学工学部 著者識別子 作成者名 所属機関 所属機関名 Research Institute of Fundamental Information Science Kyushu University 九州大学理学部附属基礎情報学研究施設 英語 Research Institute of Fundamental Information Science, Kyushu University 九州大学理学部附属基礎情報学研究施設 1992-07-20 59 Accepted Manuscript open access RIFIS Technical Report || 59 || p1-22 http://www.i.kyushu-u.ac.jp/research/report.html 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 gr...aphs 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 left(log^2 n+log m \right)$ time with $O left(n+m \right)$ processors on an EREW PRAM. For the FGS defining outerplanar graphs, we show that the refutation tree problem can be solved in $O left(log^2 n \right)$ time with $Oleft(n+rn)$ processors on an EREW PRAM. Here, n and m are the numbers of vertices and edges of an input graph, respectively.続きを見る

### 本文ファイル

rifis-tr-59 pdf 1.6 MB 234

### 詳細

レコードID 3162 査読無 Revised: April, 1993, To appear in IEICE Transactions on Information and Systems テクニカルレポート 2009.04.22 2017.01.20