Conflict-free broadcasting algorithms for graph traversals and their applications.
Journal
Parallel Computing
Journal Volume
18
Journal Issue
4
Pages
439-448
Date Issued
1992
Author(s)
Abstract
In this paper, using an adapted graph representation: double links adjacency arrays, we present conflict-free algorithms for solving some graph proglems under the single-channel broadcast communication model. These graph problems include depth first search, breadth first search, finding spanning trees, finding connected components, and finding articulation points and bridges. All the proposed algorithms broadcast 2n - 1 messages and run in O(n2 / p) time when p processors are used, where 1 < p {slanted equal to or less-than} n and n is the number of vertices. The total space requirements is O(n2). When the adjacency matrix is used to represent a graph, solving these problems requires O(n2) sequential time. Since the adjacency matrix representation can be converted into the double links adjacency arrays representation in O(n2 / p) time using p processors, the proposed algorithms are all cost-optimal. The result of this paper makes a significant improvement over Yang, Lee and Chen's work. Also, this paper reveals a fact that well-constructed data structures are useful in designing conflict-free broadcasting algorithms. © 1992.
Type
journal article