| 概要 |
Parallel algorithms have been given for solving a number of graph problems in the literatures. We can design a parallel algorithm with many processors solving a graph problem by finding the parallelis...m of the problem and assigning some parts computable in parallel to each processor. In order to gain the parallelism of a graph problem, it is required to analyze an input graph for the problem. Hence, it is important for designing a parallel algorithm to analyze the structure of a graph given as an instance of a graph problem. In this thesis, we give a new graph rewriting system which is a suitable system to analyze the structure of an input graph for a graph problem and design an efficient parallel algorithm solving the problem. Chapter 2 makes a brief review of the parallel computation theory. We introduce the parallel random access machine (PRAM) being one of the parallel computation models. The class NC represents the class of problems solvable by polylogarithmic parallel time algorithms with a polynomial number of processors on a PRAM. In Chapter 3, we define a formal graph system (FGS), as a new framework for graph rewriting, which is useful to design efficient parallel graph algorithms. An FGS is a logic program having hypergraphs instead of terms in first-order logic. We give a regular FGS which is an FGS of a special form and the family of graphs definable by a regular FGS is equal to that of graphs generated by a hyperedge replacement grammar (HRG) being one of the well-known context-free graph grammars. This result implies that regular FGSs generate trees, two-terminal series parallel (TTSP) graphs, the homeomorphisms of the given graphs, outerplanar graphs, all graphs of cyclic bandwidth $ /leq k for a constant k geq 2 $ and s-decomposable graphs for a constant S. Chapter 4 defines a refutation tree which represents explicitly the structure of a graph generated by an FGS. We consider the refutation tree problem which is to compute a refutation tree of a graph generated by an FGS. First, we present two regular FGSs generating the families of TTSP graphs and outerplanar graphs for which we devise EREW PRAM algorithms solving the refutation tree problem with $ Oleft(n + m\right) $ processors, where n and m are the numbers of vertices and edges of an input graph, respectively. The algorithm for TTSP graphs computes refutation trees in $ Oleft ((log n)^2 + log m\right) $ time. The other algorithm solves the refutation tree problem for outerplanar graphs in $ Oleft ((log n)^2)\right $ time by employing the algorithm for TTSP graphs. Many NP-complete graph problems are known to admit polynomial time algorithms, when instances are restricted to the families of graphs generated by context-free graph grammars. These results suggest that efficient parallel algorithms may be designed for a large number of NP-complete problems when input graphs are TTSP graphs and outerplanar graphs. Next, we define a notion of a simple FGS and we prove that the refutation tree problem can be solved in polynomial time for the class of simple FGSs. The purpose of Chapter 5 is to find two subclasses of simple FGSs, called sizebounded simple $ FGS_s $ and bounded simple $ FGS_s $, for which the refutation tree problem is solvable in NC. An FGS generates graphs by replacing hyperedges labeled with the same variable at a time. Hence, in order to compute a refutation tree of an input graph generated by an FGS, it may be required to solve the graph isomorphism problem deciding whether two graphs are isomorphic. The graph isomorphism problem does not seem to be solvable in polynomial time, while it is in NP. However, it has been shown that the graph isomorphism problem is in $ NC^3 $ for connected graphs of constantly bounded valence and having constantly bounded separators, and is in $ NC^2 $ for connected trees of constantly bounded valence. We prove that the refutation tree problem for a size-bounded simple FGS is $ NC^2 $ -reducible to the graph isomorphism problem for connected graphs of constantly bounded valence. This yields that the refutation tree problem for a size-bounded simple FGS can be solved in NC if connected graphs of constantly bounded valence and having constantly bounded separators are given. Moreover, we show two classes of $ FGS_s $ which are helpful to design NC algorithms for many graph problems. One is the class of size-bounded simple $ FGS_s $ which generate only undirected trees of constantly bounded valence. The other is the class of bounded simple $ FGS_s $ . For size-bounded simple $ FGS_s $ generating undirected trees of constantly bounded valence, we present an NC algorithm solving the refutation tree problem. We show that solving the graph isomorphism problem is not required for computing a refutation tree of a graph generated by a bounded simple FGS and that the refutation tree problem for a bounded simple FGS is in $ NC^2 $. The bound of valence of a given graph is an important property of $ FGS_s $ contributing to designing fast parallel algorithms for many graph problems. For graphs of constantly bounded valence, Chapter 6 shows that the coloring technique works very successfully to devise fast parallel algorithms with linear numbers of processors. By using the vertex coloring technique, we give a fast parallel algorithm for the problem VIMS(k), which is to find a maximal vertex-induced subgraph of valence at most k, where k is a given constant. This algorithm runs in $ Oleft(log^* n\right) $ time using O(n) processors on an EREW PRAM for an input graph of constantly bounded valence with n vertices. We also design an $ Oleft(log^* m\right) $ time O(m) processor EREW PRAM algorithm for the problem EIMS(k), which is to find a maximal edge-induced subgraph of degree at most k, where m is the number of edges of an input graph. Shoudai and Miyano [99, 100] and Diks et al. [23] have also given $ Oleft(log^* n\right) left(resp., O(log^* m)\right) $ time parallel algorithms for solving VIMS(k) $ left(resp., EIMS(k)\right) $ with a linear number of processors by employing the parallel maximal independent set algorithm in [44]. Since $ log^* n $ grows extremely slowly and can be viewed as a constant for all practical purposes, these algorithms are regarded as constant time parallel algorithms for all practical purposes. Hence, the constants hidden in these O-notation are very essential. Our algorithms run faster with fewer numbers of processors than their algorithms by counting these hidden constants.続きを見る
|
Mendeley出力
rifis-tr-83