Parallel graph algorithms based upon broadcast communications

Abstract

Some common guidelines that can be used to design parallel algorithms under the single-channel broadcast communication model are presented. Several graph problems are solved, including topological ordering, the connected component problem, breadth-first search, and depth-first search. If an ideal conflict resolution scheme is used, all of the algorithms require O(n) time by using n processors. Under such a situation, the algorithms are all optimal. If a realistic conflict resolution is used, the algorithms require O(n log n) time by using n/log n processors. For both cases, all of the algorithms achieve optimal speedups.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>