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(1og 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-03-31
著者
-
Miyano Satoru
Research Institute Of Fundamental Information Science Faculty Of Science Kyushu University
-
Miyano Satoru
Research Institute Of Fundamental Information Science Kyushu University
-
Uchida Tomoyuki
Research Institute of Fundamental Information Science, Kyushu University
-
Uchida Tomoyuki
Research Institute Of Fundamental Information Science Kyushu University
関連論文
- 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
- 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