Efficient Boolean Matrix and Graph Algorithms on a Bounded Parallel Computation Model

Abstract

Two efficient boolean matrix multiplication algorithms on a classical k-bounded parallel computation model are proposed. Assuming that both the boolean matrices are of size (n × n) the time complexity of the first algorithm is O (max(n²/k, na/k)) whereas that for the second algorithm is O(max (n²/k, nβ/k)) for k ≦ n, where α (≦n²) and β ≦n⌈n2⌉) are integers. These algorithms are also applied for solving several important graph problems. The cost (i e parallel running time multiplied by the number of processors used) of each of these parallel algorithms is found better compared to their existing counterparts.

Indexing terms:

• Parallel algorithms
• boolean matrix
• graph algorithms
• SIMD computer
• topological sorting
• interval DAG
• depth-first search
• connected components
• complexity