What Structural Features Make Graph Problems to Have Efficient Parallel Algorithms? : Using Outerplanar Graphs, Trapezoid Graphs and In-Tournament Graphs as Examples(Special Issue on Algorithm Engineering : Surveys)
スポンサーリンク
概要
- 論文の詳細を見る
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.
- 社団法人電子情報通信学会の論文
- 2000-03-25
著者
-
Masuyama Shigeru
The Department Of Knowledge-based Information Engineering Toyohashi University Of Technology
-
Masuyama Shigeru
The Dpartment Of Knowledge Based Information Engineering Toyohashi University Of Technology
-
NAKAYAMA Shin-ichi
The Department of Mathematical Science, Faculty of Integral Arts and Science, The University of Toku
-
Nakayama Shin-ichi
The Department Of Mathematical Science Faculty Of Integral Arts And Science The University Of Tokush
関連論文
- A LOWER BOUND OF THE EXPECTED MAXIMUM NUMBER OF VERTEX-DISJOINT s-t PATHS ON PROBABILISTIC GRAPHS
- Computing the Expected Maximum Number of Vertex-Disjoint s-t Paths in a Probabilistic Basically Series-Parallel Digraph
- Inequalities on the Number of Connected Spanning Subgraphs in a Multigraph
- What Structural Features Make Graph Problems to Have Efficient Parallel Algorithms? : Using Outerplanar Graphs, Trapezoid Graphs and In-Tournament Graphs as Examples(Special Issue on Algorithm Engineering : Surveys)
- An Algorithm for Finding Two Edge-Disjoint Paths in Tournaments
- Parallel Algorithms for Finding a Hamiltonian Path and a Hamiltonian Cycle in an In-Tournament Graph(Special Section on Discrete Mathematics and Its Applications)