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


 
 

 

A Practical Parallel Algorithm for Cycle Detection in Partitioned Digraphs

Graph theoretic techniques are used in variety of important computational problems in the areas of computational physics, mechanics, and fluid flow. We present a new, parallel algorithm for detecting cycles in partitioned, directed graphs that is both scalable in the graph and machine size, and performs well in practice. As an example, on a $p = 64$ processor cluster, we have solved an extremely large and difficult input problem with $n = 2^{28}$ vertices in less than five minutes. Our parallel algorithm uses a new graph representation, called Packed-Intervals, has a theoretical running time for this input of $\tau \log p + \bigO{\frac{n}{p}} \sigma + \bigO{\frac{n}{p}}$ for $n \geq p^{4}$, and achieves good speedup for any $n \gg p$ in practice. Our study includes both an efficient parallel algorithm and an experimental study.

Publication History

Versions of this paper appeared as:
  1. University of New Mexico AHPCC-TR-99-013

Download this report in Adobe PDF

 

 
 

Last updated: July 26, 2004

 




Computational Biology



Parallel Computing



Combinatorics