Reducing conflict resolution time for solving graph problems in broadcast communications |
| |
Authors: | Chang-Biau Yang |
| |
Affiliation: | Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung, Taiwan80424, ROC |
| |
Abstract: | In this paper, we propose some algorithms to solve the topological ordering problem, the breadth-first search problem and the connected component problem under the broadcast communication model. The basic idea of our algorithms is to divide a graph into several layers. Only after all vertices in one layer are processed, we begin to process the vertices in another layer. Thus, the number of broadcast conflicts is reduced. We also propose a randomized conflict resolution scheme to resolve conflicts. We show that the average time complexity of our algorithms is Θ(n), where n is the number of available processors and also the number of vertices in the graph. |
| |
Keywords: | Parallel algorithms broadcast communication graph topological ordering breadth-first search connected component |
本文献已被 ScienceDirect 等数据库收录! |
|