An Optimal Parallel Algorithm for Constructing a Spanning Tree on Proper Circle Trapezoid Graphs ()
ABSTRACT
Given a simple graph G with n vertices and m edges, the spanning tree problem is to find a spanning tree
for a given graph G. This problem has
many applications, such as electric power systems, computer network design and
circuit analysis. For a simple graph, the spanning tree problem can be solved
in O(log n) time with O(m+n) processors on the CRCW
PRAM. In general, it is known that more efficient parallel algorithms can be
developed by restricting classes of graphs. In this paper, we shall propose a
parallel algorithm which runs O(log n) time with O(n/log n) processors on the EREW PRAM for constructing
on proper circle trapezoid graphs.
Share and Cite:
Honma, H. , Nakajima, Y. , Nagasaki, S. and Sasaki, A. (2018) An Optimal Parallel Algorithm for Constructing a Spanning Tree on Proper Circle Trapezoid Graphs.
Journal of Applied Mathematics and Physics,
6, 1649-1658. doi:
10.4236/jamp.2018.68141.
Cited by
No relevant information.