MISC

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

エクスポート
BibTeX RIS