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
본 논문에서는 그래프 문제의 어떤 구조적 특징이 효율적인 병렬 알고리즘을 가능하게 하는지 분석한다. 우리는 외부 평면 그래프, 사다리꼴 그래프, 토너먼트 내 그래프의 세 가지 그래프에 대한 일반적인 문제에 대한 몇 가지 병렬 알고리즘을 조사합니다. 외부 평면 그래프의 최단 경로 문제, 최장 경로 문제 및 최대 흐름 문제, 사다리꼴 그래프의 최소 무게 연결 지배 집합 문제 및 색상 문제, 토너먼트 내 그래프의 해밀턴 경로 및 해밀턴 사이클 문제에 대한 결과가 채택됩니다. 작업 사례로.
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.
부
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
부
@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},}
부
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 -