Multiprocessor Implementation of Transitive Closure

Abstract

Graph theoretic algorithms are found quite effective for solving complex real life problems. Computing the transitive closure in directed graphs is a fundamental graph problem. Transitive closure can be thought of as establishing a data structure that makes it possible to solve reachability questions (can I get to x from y?) efficiently. After the preprocessing of constructing the transitive closure, all reachability queries can be answered in constant time by simply reporting a matrix entry. Transitive closure is fundamental in propagating the consequences of modified attributes of a graph G. For efficient system utilization and fast response to the user, it is necessary to use parallel algorithms for solving a single problem. Transitive closure is a highly parallelizable problem; it belongs to the class NC of problems that can be solved in polylogarithmic time (i.e. O(logcn) for some constant c) with polynomial number of processors.