A Practical Parallel Algorithm for Cycle Detection in Partitioned Digraphs
David A. Bader · 1999
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 tlog p #O # n p # s#O # n p # for n # p 4 , and achieves good speedup for any n # p in practice. Our study includes both an efficient parallel algorithm and an experimental study. Please see http://www.eece.unm.edu/dbader for additional information. Keywords Cycle Detection, Graph Theory, Experimental Parallel Algorithms, Parallel Performance. UNM Technical Report: EE...