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

作　　者：Hirotoshi Honma Yoko Nakajima Shino Nagasaki Atsushi Sasaki 

机构地区：[1]National Institute of Technology, Kushiro College, Kushiro, Japan

出　　处：《Journal of Applied Mathematics and Physics》2018年第8期1649-1658,共10页应用数学与应用物理（英文）

摘　　要：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.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.

关 键 词：Design and Analysis of Parallel Algorithms PROPER Circle TRAPEZOID GRAPHS SPANNING Tree 

分 类 号：O1[理学—数学]