David A. Bader
IEEE Fellow
AAAS Fellow
Professor
College of Computing
Georgia Tech
Atlanta, GA 30332


 
 

 

The Euler Tour Technique and Parallel Rooted Spanning Tree

Many parallel algorithms for graph problems start with finding a spanning tree and rooting the tree to define some structural relationship on the vertices which can be used by following problem specific computations. The generic procedure is to find an unrooted spanning tree and then root the spanning tree using the Euler tour technique. With a randomized work-time optimal unrooted spanning tree algorithm and work-time optimal list ranking, finding rooted spanning trees can be done work-time optimally on EREW PRAM w.h.p. Yet the Euler tour technique assumes as ``given'' a circular adjacency list, it is not without implications though to construct the circular adjacency list for the spanning tree found on the fly by a spanning tree algorithm. In fact our experiments show that this ``hidden'' step of constructing a circular adjacency list could take as much time as both spanning tree and list ranking combined. In this paper we present new efficient algorithms that find rooted spanning trees without using the Euler tour technique and incur little or no overhead over the underlying spanning tree algorithms.

We also present two new approaches that construct Euler tours efficiently when the circular adjacency list is not given. One is a deterministic PRAM algorithm and the other is a randomized algorithm in the SMP model.The randomized algorithm takes a novel approach to the problems of constructing Euler tour and rooting a tree. It computes a rooted spanning tree first, then constructs a Euler tour directly for the tree using depth-first traversal. The tour constructed is cache-friendly with adjacent edges in the tour stored in consequtive locations of an array so that prefix-sum (scan) can be used for tree computations instead of the more expensive list-ranking.

 

Publication History

Versions of this paper appeared as:
  1. G. Cong and D.A. Bader, ``The Euler Tour Technique and Parallel Rooted Spanning Tree,'' Technical Report, February 2004.
  2. G. Cong and D.A. Bader, ``The Euler Tour Technique and Parallel Rooted Spanning Tree,'' 33rd International Conference on Parallel Processing (ICPP), Montreal, Canada, pages 448-457, August 2004.

Download this report in Adobe PDF

 

 
 

Last updated: August 19, 2004

 




Computational Biology



Parallel Computing



Combinatorics