|
|
Please login using the form on menu list.
It is required to login for Full-Text PDF.
|
What Structural Features Make Graph Problems to Have Efficient Parallel Algorithms? --Using Outerplanar Graphs, Trapezoid Graphs and In-Tournament Graphs as Examples--
Shigeru MASUYAMA
Shin-ichi NAKAYAMA
Publication
IEICE TRANSACTIONS on Information and Systems Vol.E83-D No.3 pp.541-549
Publication Date: 2000/03/20
Online ISSN:
Print ISSN: 0916-8532
Type of Manuscript: INVITED SURVEY PAPER
Category: Parallel and Distributed Algorithms
Keyword:
parallel graph algorithms,
structure and complexity,
outerplanar graph,
trapezoid graph,
in-tournament graph,
Full Text: PDF
Summary:
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, trapezoid 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.
|
|
