Parallel Algorithms for Maximal Linear Forests

スポンサーリンク

概要

• 論文の詳細を見る

• The maximal linear forest problem is to find, given a graph G = (V, E), a maximal subset of V that induces a linear forest. Three parallel algorithms for this problem are presented. The first one is randomized and runs in O(log n) expected time using n^2 processors on a CRCW PRAM. The second one is deterministic and runs in O(log^2n) timeusing n^4 processors on an EREW PRAM. The last one is deterministic and runs in O(log^5n) time using n^3 processors on an EREW PRAM. The results put the problem in the class NC.

• 社団法人電子情報通信学会の論文
• 1997-04-25

著者

• Uehara R

  Tokyo Woman's Christian Univ.

• Uehara Ryuhei

  Center For Information Science Tokyo Woman's Christian University Tokyo

• CHEN Zhi-Zhong

  Department of Mathematical Sciences, Tokyo Denki University

• Chen Zhi-zhong

  Department Of Mathematical Sciences Tokyo Denki University

• Chen Zhi-zhong

  Department Of Computer Science And Information Mathematics University Of Electro-communications

関連論文

• Parallel Algorithms for Maximal Linear Forests
• Study of Photocurrent Properties of GaN Ultraviolet Photoconductor Grown on 6H-SiC Substrate
• Computing Bounded-Degree Phylogenetic Roots of Disconnected Graphs
• More Reliable Protein NMR Peak Assignment via Improved 2-Interval Scheduling (New Aspects of Theoretical Computer Science)
• The Complexity of Selecting Maximal Solutions
• Finding Maximal Cycle-Free Subgraphs in Parallel(Fundamental Studies on Computational Complexity)
• A Deterministic Approximation Algorithm for Maximum 2-Path Packing
• Grammatical Characterizations of P and PSPACE
• Parallel Algorithms for the Maximal Tree Cover Problems

スポンサーリンク