1998年12月18日
区間グラフにおける全域森構築のための最適並列アルゴリズム
釧路工業高等専門学校紀要
- 巻
- 32
- 号
- 開始ページ
- 55
- 終了ページ
- 58
- 記述言語
- 日本語
- 掲載種別
- 出版者・発行元
- 釧路工業高等専門学校
Let G=(V, E) be a simple graph with n vertices, m edges and p connected components. The problem of constructing a spanning forest is to find a spanning tree for each connected component of G. For a simple graph, Chin et al.[4] demonstrated that a spanning forest can be found in O(log^2 n) time using O(n^2/log^2 n) processors. In this paper, we propose an O(log n) time parallel algorithm with O(n/log n) processors on the EREW PRAM for constructing a spanning forest on Interval graphs.
- リンク情報
-
- CiNii Articles
- http://ci.nii.ac.jp/naid/110000062705
- CiNii Books
- http://ci.nii.ac.jp/ncid/AN00065852
- URL
- http://id.ndl.go.jp/bib/106025
- ID情報
-
- ISSN : 0455-017X
- CiNii Articles ID : 110000062705
- CiNii Books ID : AN00065852