Transitive closure algorithms based on graph traversal

• DOI: 10.1145/155271.155273
• Publication Date: 2002-07-27T11:29:00Z
• Authors: Yannis Ioannidis; Raghu Ramakrishnan; Linda Winger
• Keywords: Transitive closure; Transitive reduction; Graph traversal; Traverse

Several graph-based algorithms have been proposed in the literature to compute transitive closure of a directed graph. We develop two new (Basic_TC and Gobal_DFTC) compare performance their implementations disk-based environment with well-known algorithm by Schmitz. Our use depth-first search traverse graph technique called marking avoid processing some arcs They nodes reverse topological order, building descendent sets adding children. While details these differ considerably, one important difference among them is time at which set additions are performed. Basic_TC, results superior performance. The first reason that early result larger sizes on average over duration execution, thereby causing more I/O; very often this turns out than offset gains not having fetch certain again add them. second information collected pass can be used apply several optimizations pass. To extent possible, we also adapt perform path computations. Again, our comparison confirms trends seen reachability queries. Taken conjunction another study indicate all significantly outperform other types such as Seminaive Warren.