Journal of Applied Mathematics and Physics

Volume 6, Issue 8 (August 2018)

ISSN Print: 2327-4352   ISSN Online: 2327-4379

Google-based Impact Factor: 0.63  Citations  

An Optimal Parallel Algorithm for Constructing a Spanning Tree on Proper Circle Trapezoid Graphs

HTML  XML Download Download as PDF (Size: 608KB)  PP. 1649-1658  
DOI: 10.4236/jamp.2018.68141    364 Downloads   617 Views  

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.

Copyright © 2021 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.