A BSP/CGM algorithm for computing Euler tours in graphs

  • E. N. Caceres UFMS
  • C. Y. Nasu UFMS

Resumo


We describe a parallel algorithm using the BSP/CGM model (Bulk Synchronous Parallel/Coarse Grained Multicomputer) to obtain the Euler tours in graphs. It is based on the PRAM (parallel random access machine) algorithm by Caceres et al. For an input graph of n vertices and m edges, the algorithm requires local computation time of O((m+n)/p), O((m+n'p) memory and O(logp) communication rounds, where p is the number of processors. To our knowledge there are no other parallel algorithms under the coarse-grained models for the Euler tours in graphs. The proposed algorithm is implemented using MPI (message passing interface) and the C language. The parallel program runs on a Beowulf with 66 nodes. The implementation results confirm the theoretical complexity results of the algorithm.
Palavras-chave: User-generated content, Bridges, Parallel algorithms, Phase change random access memory, Cities and towns, Message passing, Graph theory, Rivers, Search methods, Data structures
Publicado
10/11/2003
Como Citar

Selecione um Formato
CACERES, E. N.; NASU, C. Y.. A BSP/CGM algorithm for computing Euler tours in graphs. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 15. , 2003, São Paulo/SP. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2003 . p. 175-182.