TITLE:
An Optimal Parallel Algorithm for Constructing a Spanning Tree on Proper Circle Trapezoid Graphs
AUTHORS:
Hirotoshi Honma, Yoko Nakajima, Shino Nagasaki, Atsushi Sasaki
KEYWORDS:
Design and Analysis of Parallel Algorithms, Proper Circle Trapezoid Graphs, Spanning Tree
JOURNAL NAME:
Journal of Applied Mathematics and Physics,
Vol.6 No.8,
August
14,
2018
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.