What Structural Features Make Graph Problems to Have Efficient Parallel Algorithms? - Using Outerplanar Graphs, Trapezoid Graphs and In-Tourament Graphs as Examples -

38 References
  • MASUYAMA Shigeru
    Department of Knowledge-Based Information Engineering, Toyohashi University of Technology
  • NAKAYAMA Shin-ichi
    Department of Mathematical Sciences, Faculty of Integral Arts and Sciences, The University of Tokushima

Search this article

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, 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.

Journal

References(38)*help

See more

Keywords

Details 詳細情報について

  • CRID
    1570291227534662784
  • NII Article ID
    110003210260
  • NII Book ID
    AA10826272
  • ISSN
    09168532
  • Text Lang
    en
  • Data Source
    • CiNii Articles

Report a problem

Back to top