The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Cet article analyse quelles caractéristiques structurelles des problèmes de graphes permettent des algorithmes parallèles efficaces. Nous étudions quelques algorithmes parallèles pour des problèmes typiques sur trois types de graphiques, les graphiques planaires externes, les graphiques trapézoïdaux et les graphiques en tournoi. Nos résultats sur le problème du chemin le plus court, le problème du chemin le plus long et le problème du flux maximum sur les graphes planaires externes, le problème de l'ensemble dominant connecté de poids minimum et le problème de coloration sur les graphes trapézoïdaux et le problème du chemin hamiltonien et du cycle hamiltonien sur les graphes en tournoi sont adoptés. comme exemples concrets.
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.
Copier
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
Copier
@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},}
Copier
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 -