What Structural Features Make Graph Problems to Have Efficient Parallel Algorithms? --Using Outerplanar Graphs, Trapezoid Graphs and In-Tournament Graphs as Examples--
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E83-D No.3 pp.541-549
- Publication Date
- 2000/03/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- INVITED SURVEY PAPER
- Category
- Parallel and Distributed Algorithms
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Shigeru MASUYAMA, Shin-ichi NAKAYAMA, "What Structural Features Make Graph Problems to Have Efficient Parallel Algorithms? --Using Outerplanar Graphs, Trapezoid Graphs and In-Tournament Graphs as Examples--" in IEICE TRANSACTIONS on Information,
vol. E83-D, no. 3, pp. 541-549, March 2000, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e83-d_3_541/_p
Copy
@ARTICLE{e83-d_3_541,
author={Shigeru MASUYAMA, Shin-ichi NAKAYAMA, },
journal={IEICE TRANSACTIONS on Information},
title={What Structural Features Make Graph Problems to Have Efficient Parallel Algorithms? --Using Outerplanar Graphs, Trapezoid Graphs and In-Tournament Graphs as Examples--},
year={2000},
volume={E83-D},
number={3},
pages={541-549},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={March},}
Copy
TY - JOUR
TI - What Structural Features Make Graph Problems to Have Efficient Parallel Algorithms? --Using Outerplanar Graphs, Trapezoid Graphs and In-Tournament Graphs as Examples--
T2 - IEICE TRANSACTIONS on Information
SP - 541
EP - 549
AU - Shigeru MASUYAMA
AU - Shin-ichi NAKAYAMA
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E83-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2000
AB - 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.
ER -
English
