Result: An efficient parallel algorithm for constructing a breadth first searching tree of a trapezoid graph

Summary: Let \(G=(V,E)\) be a simple graph with \(n\) vertices, \(m\) edges. The problem of constructing a spanning tree is of great interest in various domains such as computer science, genetices, archaeology and ecology. For a simple graph, \textit{F. Y. Chin}, \textit{J. Lam} and \textit{I. Chen} [Commun. ACM 25, 659--665 (1982; Zbl 0485.68056)] demonstrated that a spanning forest can be found in \(O(\log^2n)\) time using \(O(n^2/ \log^2n)\) processors. Further, \textit{H. C. Chen} and \textit{Y. L. Wang} [A linear time algorithm for finding depth-first spanning trees on trapezoid graphs, Inf. Process. Lett. 63, 13--18 (1997)] presented a linear time sequential algorithm for finding depth-first spanning trees on trapezoid graph. In this paper, we propose an \(O(\log^2n)\) time parallel algorithm with \(O(n)\) processors on the EREW PRAM for constructing a breadth first searching tree on trapezoid graphs.