Proceedings on Seventh International Conference on Information Visualization, 2003. IV 2003.
Download PDF

Abstract

Abstract In this paper, we propose a new algorithm for computing recursive closures. The main idea behind this algorithm is tree labeling and graph decomposition, based on which the transitive closure of a directed graph can be computed in O(e?dmax?dout) time and in O(n?dmax?dout) space, where n is the number of the nodes of the graph, e is the numbers of the edges, d max is the maximal indegree of the nodes, and dout is the average outdegree of the nodes. Especially, this method can be used to efficiently compute recursive relationships of a directed graph in a relational environment.
Like what you’re reading?
Already a member?Sign In
Member Price
$11
Non-Member Price
$21
Add to CartSign In
Get this article FREE with a new membership!

Related Articles