Work-efficient BSR-based parallel algorithms for some fundamental problems in graph theory |
| |
Authors: | Jean-Frédéric Myoupo David Semé |
| |
Affiliation: | (1) Laboratoire de Recherche en Informatique d’Amiens (LaRIA), Université de Picardie Jules Verne, Faculté de Mathématiques et d’Informatique, 33 rue Saint-Leu, 80039 Amiens Cedex 1, France |
| |
Abstract: | This paper presents BSR-parallel algorithms for some problems in fundamental graph theory : transitive closure, connected
components, spanning tree, bridges and articulation points of a graph and bipartite graph recognition. There already exist
constant time algorithms to solve these problems on a mesh with reconfigurable bus system using O(N
4) processors. Here we show that these problems can be solved in constant time using only O(N
2) processors on the BSR model (N is the number of vertices of the graph G). Therefore, our algorithms are more work-efficient. These new results suggest that many other problems in graph theory can
be solved in constant time using the BSR model. |
| |
Keywords: | Broadcast CRCW PRAM Parallel algorithm Reduction Selection Graph theory Transitive closure Connected components Spanning tree Bridge Articulation point Bipartite graph |
本文献已被 SpringerLink 等数据库收录! |