What Structural Features Make Graph Problems to Have Efficient Parallel Algorithms? - Using Outerplanar Graphs, Trapezoid Graphs and In-Tourament Graphs as Examples -
-
- MASUYAMA Shigeru
- Department of Knowledge-Based Information Engineering, Toyohashi University of Technology
-
- NAKAYAMA Shin-ichi
- Department of Mathematical Sciences, Faculty of Integral Arts and Sciences, The University of Tokushima
この論文をさがす
抄録
This paper analyzes what structural features of graph problems allow efficient parallel algorithms. We survey some parallel algorithms for typical problems on three kinds of graphs, outerplanar graphs, trapeziod graphs and in-tournament graphs. Our results on the shortest path problem, the longest path problem and the maximum flow problem on outerplanar graphs, the minimum-weight connected dominating set problem and the coloring problem on trapezoid graphs and Hamiltonian path and Hamiltonian cycle problem on in-tournament graphs are adopted as working examples.
収録刊行物
-
- IEICE transactions on information and systems
-
IEICE transactions on information and systems 83 (3), 541-549, 2000-03-25
一般社団法人電子情報通信学会
- Tweet
キーワード
詳細情報 詳細情報について
-
- CRID
- 1570291227534662784
-
- NII論文ID
- 110003210260
-
- NII書誌ID
- AA10826272
-
- ISSN
- 09168532
-
- 本文言語コード
- en
-
- データソース種別
-
- CiNii Articles