区間グラフにおける全域森構築のための最適並列アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
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.
- 釧路工業高等専門学校の論文
- 1998-12-18
著者
関連論文
- 多変量解析によるプロ野球選手(読売巨人軍)の次期年俸推定
- NP完全問題における効率的近似解法に関する研究
- An Optimal Parallel Algorithm for Hinge Vertex Probrem of a Circular-Arc Graph
- 1-D-7 Circular Permutation Graphの関節点,橋検出アルゴリズム(離散・組合せ最適化(3))
- 1-D-2 台形グラフにおけるMFVS問題のための効率的アルゴリズム(離散・組合せ最適化(1))
- 2-E-10 Circular Permutation Graph上の要節点導出のための最適並列アルゴリズム(離散最適化(3))
- LISPマシーンにおけるマイクロコンパイラの開発
- 超音波パルス法 その一 装置
- 多変量解析によるプロ野球選手の次期年俸額推定(投手編)
- A parallel algorithm for finding all hinge vertices of a Circular-Arc graph
- A parallel algorithm for finding all hinge vertices of a trapezoid graph (New Developments of Theory of Computation and Algorithms)
- Circular-arcグラフにおける全要節点を求める並列アルゴリズム
- 台形グラフにおける全関節節点を求める並列アルゴリズム(グラフ・ネットワーク)
- 区間グラフにおける全関節節点を求める並列アルゴリズム(グラフ・ネットワーク(1))
- An O (log n) time Parallel Algorithm from Constructing a Spanning Forest on Trapezoid Graphs
- An $0(log n)$ parallel algorithm for constructing a spanning forest on Trapezoid graphs
- 台形グラフにおける全域林構築のためのO(log n)並列アルゴリズム(グラフ・ネットワーク(2))
- 形成評価システムによる工学基礎教育
- パソコンを使った重量計
- マイコンによる成績集計システム(VII)
- マイコンによる成績集計システム(VI)
- マイコンによる成績集計システム(V)
- マイコンによる成績集計システム(IV)
- マイコンによる成績集計システム(III)
- マイコンによる成績集計システム(II)
- 階層分析法による情報処理技術者試験第2種合否判定システムの開発
- 台形グラフにおける全域森構築のための最適並列アルゴリズム
- 台形グラフにおける幅優先探索木構築のための効率的並列アルゴリズム
- TSPにおける遺伝並列アルゴリズム
- 区間グラフにおける全域森構築のための最適並列アルゴリズム
- 完全3ハイパーグラフにおけるハイパーハミルトニアンサイクル分解に関 する研究
- 知識を用いたマイクロコンパイラの最適化
- n-Alcohol C_1〜C_5中に於ける超音波伝播について
- マイコンによる成績集計システム(I)
- 超音波エコーパルス間隔測定器
- ディジタル・ボックスカー積算器
- 半導体物性測定のデータ処理
- Ultrasonic Absorption in Tellurium
- Some Elastic Constants of Tellurium between 85°K and 300°K
- Ultrasonic Absorption in Single Crystal Bismuth from 140°K to 273°K
- Hall Mobility of Tellurium from 170°K to 345°K
- Longitudinal Acoustic Velocity and Ultrasonic Attenuation in Ferroelectric Lithium Hydrazinium Sulphate,Li(N_2H_5)SO_4 from 15-140°C
- 2-I-1 影響度最大の要節点導出のための効率的アルゴリズム(離散最適化(3))
- 1-B-6 非退化型円弧グラフにおけるMFVS問題解決アルゴリズム(離散最適化(2))
- 1-B-5 環状型台形グラフの全域木導出のための最適アルゴリズム(離散最適化(2))
- 交差グラフにおける離散最適化問題を解く効率的アルゴリズムの開発
- An Optimal Algorithm for Finding Articulation Vertex of Circular Permutation Graphs