A Parallel Algorithm for the Maximal Co-Hitting Set Problem
スポンサーリンク
概要
- 論文の詳細を見る
Let C={c_1,…,c_m} be a family of subsets of a finite set S={1,…,n}, a subset S′of S is a co-hitting set if S′ contains no element of C as a subset. By using an O(log n)^2) time EREW PRAM algorithm for a maximal independent set problem (MIS), we show that a maximal co-hitting set for S can be computed on an EREW PRAM in time O(αβ(log(n+m))^2) using O(n^2m) processors, where α=max{|c_i‖i=1,…,n} and β=max{|d_j‖=1,…,n} with d_j={c_i|j∈c_i}. This implies that if αβ=O((log(n+m))^k) then the problem is solvable in NC.
- 社団法人電子情報通信学会の論文
- 1993-02-25
著者
-
Miyano Satoru
Research Institute Of Fundamental Information Science Faculty Of Science Kyushu University
-
Shoudai T
Department Of Informatics Kyushu University
-
Shoudai Takayoshi
Faculty Of 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