<テクニカルレポート>
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 $ kappa $ , where $ kappa $ 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 mid V mid = 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 = mid Emid. For constant degree graphs, we show that the coloring technique works very successfully to devise faster parallel algorithms with less number of processors.続きを見る

本文情報を非表示

rifis-tr-34 pdf 731 KB 53  

詳細

レコードID
査読有無
関連情報
注記
タイプ
登録日 2009.04.22
更新日 2017.01.20