An Optimal Parallel Algorithm for Constructing a Spanning Tree on Proper Circle Trapezoid Graphs - Journal of Applied Mathematics and Physics

JAMP > Vol.6 No.8, August 2018

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

HTML XML

Download as PDF (Size: 608KB) PP. 1649-1658

DOI: 10.4236/jamp.2018.68141 553 Downloads 1,157 Views

Author(s)

Hirotoshi Honma, Yoko Nakajima, Shino Nagasaki, Atsushi Sasaki

Affiliation(s)

National Institute of Technology, Kushiro College, Kushiro, Japan.

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.

KEYWORDS

Design and Analysis of Parallel Algorithms, Proper Circle Trapezoid Graphs, Spanning Tree

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.

Journals Menu

Follow SCIRP

	+1 323-425-8868
	customer@scirp.org
	+86 18163351462(WhatsApp)
	1655362766

	Paper Publishing WeChat

Journals Menu

Home

About SCIRP

Service

Policies