| In this paper, we consider parallel algorithms for shortest paths and related problems on trapezoid graphs under the CREW PRAM model. Given a trapezoid graph with n vertices, we present parallel algorithms solving the following problems: For the single-source shortest path problem, the algorithm runs in O(log n) time using O(n) processors and space. For the all-pair shortest path query problem, after spending O(log n) preprocessing time using O(n log n) space and O(n) processors, the algorithm can answer the query in O(log £_) time using one processor. Here £_ denotes the distance between two queried vertices. For the minimum cardinality Steiner set problem, the algorithm runs in O(log n) time using O(n) processors and space. We also extend our results to the generalized trapezoid graphs. The single-source shortest path problem and the minimum cardinality Steiner set problem on d-trapezoid graphs and circular d-trapezoid graphs can both be solved in O(log n log d) time using O(nd) space and O(d n / log d) processors. The all-pair shortest path query problem on d-trapezoid graphs and circular d-trapezoid graphs can be answered in O(d log£_) time using one processor after spending O(log n log d) preprocessing time using O(nd log n) space and O(d n / log d) processors. |