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

作成者 作成者姓名 Uchida, Tomoyuki 内田, 智之 所属機関 所属機関名 Department of Information Systems Kyushu University 九州大学大学院総合理工学研究科情報システム学専攻 作成者姓名 Shoudai, Takayoshi 正代, 隆義 所属機関 所属機関名 Faculty of Engineering, Yamaguchi University 山口大学工学部 作成者姓名 Miyano, Satoru 宮野, 悟 所属機関 所属機関名 Research Institute of Fundamental Information Science Kyushu University 九州大学理学部附属基礎情報学研究施設 英語 Research Institute of Fundamental Information Science, Kyushu University 九州大学理学部附属基礎情報学研究施設 1992-07-20 RIFIS Technical Report 59 accepted open access 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 121

### 詳細

レコードID 3162 査読無 RIFIS Technical Report || 59 || p1-22 http://www.i.kyushu-u.ac.jp/research/report.html Revised: April, 1993, To appear in IEICE Transactions on Information and Systems テクニカルレポート 2009.04.22 2017.01.20