Y. Chen (Canada)
digraph, transitive closure, branching, tree la beling, topological order
In this paper, we propose a new algorithm for computing transitive closures. The main idea behind this is tree labeling and graph decomposition, based on which the transitive closure of a directed graph can be computed in O(eb) time and O(nb) space, where n is the number of the nodes of the graph, e is the numbers of the edges, and b is the graph's breadth. Especially, this method hints a new way to speed up the computation of recursion in relational databases.
Important Links:
Go Back
