An Algorithm to Compute Transitive Closure Matrix for Acyclic Dirtcted Graph

Abstract

Warshall proposed an algorithm to compute the transitive closure matrix for any directed graph in 1962. Over the past four decades, it has been widely applied to various applications. However, no matter what kind of directed graph it is, this algorithm requires O(n3) time. In fact, there are many applications of the transitive closure matrix just for acyclic directed graph, and do finding it efficiently is important. In this paper, a fast algorithm is proposed to compute the transitive closure for the acyclic directed graph. This algorithm takes O(k*n) time for an acyclic directed graph with n vertices and k edges.