文献

J-GLOBAL ID：201702265905102143   整理番号：17A0621787

特定クラスの円台形グラフ上でスパンニング木を構築するための並列アルゴリズム

Parallel Algorithm for Constructing a Spanning Tree on a Certain Class of Circle Trapezoid Graphs

著者 (2件)： HONMA Hirotoshi (Kushiro Coll.) ,  NAKAJIMA Yoko (Kushiro Coll.)
資料名： 釧路工業高等専門学校紀要(Web)  (Research Reports. Kushiro National College of Technology (Web))
号： 50  ページ： 52-57 (WEB ONLY)  発行年： 2017年03月 
JST資料番号： U0872A  ISSN： 2432-6844  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： n頂点の単純な連結グラフGにおけるスパンニング木問題は,Gの全頂点を連結する木を見つけることである。この問題には,電力系統,計算機ネットワーク設計や回路解析等の多くの用途がある。単純なグラフであるため,スパンニング木問題は,CRCW PRAMでO(n+m)プロセッサを用いて,O(log n)時間で解法できる。グラフの階数を制限することで,一層効率的な並列アルゴリズムが開発可能で,近年,順序アルゴリズムを並列化するための多くの研究がなされている。本論文では,特定クラスの円台形グラフ上でスパンニング木を構築するための,CRCW PRAMでO(n=log n)プロセッサを用いてO(log n)時間演算する並列アルゴリズムを提案している。将来的に,本研究結果を他のグラフに拡大するために,研究を継続していく。

シソーラス用語： *スパンニング木 ,  *グラフ ,  *並列アルゴリズム ,  計算量 ,  *CPU時間 ,  *演算プロセッサ ,  並列化 ,  数値 ,  計算機網 ,  回路解析 ,  頂点 ,  *並列演算
準シソーラス用語： *連結グラフ ,  CRCW PRAM ,  階数 ,  計算機ネットワーク

分類 (1件)： 演算方式  (JC02020Z)

タイトルに関連する用語 (7件)： クラス ,  円 ,  台形 ,  グラフ ,  スパンニング木 ,  構築 ,  並列アルゴリズム