O(log^* n) Time Parallel Algorithm for Computing Bounded degree Maximal Subgraphs
スポンサーリンク
概要
- 論文の詳細を見る
By using the vertex coloring technique, we give a fast parallel algorithm that finds a maximal vertex-induced subgraph of degree at most k, where k is a given constant. This algorithm runs in O(log^* n) time using O (n) processors on an EREW PRAM for a constant degree graph G=(V,E) with |V|=n. We also describe an O(log^* m) time O(m) processor EREW PRAM algorithm for finding a maximal edge-induced subgraph of degree at most k, where m=|E|. For constant degree graphs, we show that the coloring technique works very successfully to devise faster parallel algorithms with fewer numbers of processors.
- 一般社団法人情報処理学会の論文
- 1993-01-15
著者
-
Miyano Satoru
Research Institute Of Fundamental Information Science Faculty Of Science Kyushu University
-
Uchida T
Graduate School Of Information Sciences Hiroshima City University
-
Uchida Tomoyuki
Research Institute of Fundamental Information Science, Kyushu University
-
Uchida Tomoyuki
Research Institute Of Fundamental Information Science Kyushu University
関連論文
- Discovering Knowledge from Graph Structured Data by Using Refutably Inductive Inference of Formal Graph Systems (Special lssue on Selected Papers from LA Synposium)
- Knowledge Acquisition from Amino Sequences by Machine Learning System BONSAI
- Learning Theory Toward Genome Informatics
- A New Series of $\Delta^p_2$-Complete Problems
- Systematized Approaches to the Complexity of Subgraph Problems
- Parallel Algorithms for Refutation Tree Problem on Formal Graph Systems
- Using Maximal Independent Sets to Solve Problems in Parallel
- Learning of Finite Unions of Tree Patterns with Internal Structured Variables from Queries
- Polynomial Time Inductive Inference of TTSP Graph Languages from Positive Data
- O(log^* n) Time Parallel Algorithm for Computing Bounded degree Maximal Subgraphs
- A Parallel Algorithm for the Maximal Co-Hitting Set Problem
- O(log^* n) Time Parallel Algorithm for Computing Bounded Degree Maximal Subgraphs
- Complexity of Finding Alphabet Indexing
- O(log^* n) Time Parallel Algorithm for Computing Bounded Degree Maximal Subgraphs