Mixed-Approach Algorithms for Transitive Closure.

Håkan Jakobsson: Mixed-Approach Algorithms for Transitive Closure. PODS 1991: 199-205
  author    = {H{\aa}kan Jakobsson},
  title     = {Mixed-Approach Algorithms for Transitive Closure},
  booktitle = {Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, May 29-31, 1991, Denver, Colorado},
  publisher = {ACM Press},
  year      = {1991},
  isbn      = {0-89791-430-9},
  pages     = {199-205},
  ee        = {, db/conf/pods/Jakobsson91.html},
  crossref  = {DBLP:conf/pods/91},
  bibsource = {DBLP,}


We study two different approaches for computing the transitive closure of a directed graph and show that, in some sense, they are "dual" on edge-reversed graphs but, nevertheless, can differ asymptotically in cost on the same family of graphs. We show how the two approaches can be mixed into a new algorithm using reachability trees. We show that the new algorithm is O(Sigma(x,y) in V×VCONN(x, y)) where CONN(x, y) is the pairwise connectivity of x and y, and give a more exact connectivity-based upper bound that is better than the lower bound for a wide class of other algorithms on every family of graphs.

Copyright © 1991 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 29-31, 1991, Denver, Colorado. ACM Press 1991, ISBN 0-89791-430-9
Contents BibTeX

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 562 KB]


Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
Don Coppersmith, Shmuel Winograd: Matrix Multiplication via Arithmetic Progressions. STOC 1987: 1-6 BibTeX
Jürgen Ebert: A Sensitive Transitive Closure Algorithm. Inf. Process. Lett. 12(5): 255-258(1981) BibTeX
Yannis E. Ioannidis, Raghu Ramakrishnan: Efficient Transitive Closure Algorithms. VLDB 1988: 382-394 BibTeX
Giuseppe F. Italiano: Amortized Efficiency of a Path Retrieval Data Structure. Theor. Comput. Sci. 48(3): 273-281(1986) BibTeX
Giuseppe F. Italiano: Finding Paths and Deleting Edges in Directed Acyclic Graphs. Inf. Process. Lett. 28(1): 5-11(1988) BibTeX
J. Ian Munro: Efficient Determination of the Transitive Closure of a Directed Graph. Inf. Process. Lett. 1(2): 56-58(1971) BibTeX
Claus-Peter Schnorr: An Algorithm for Transitive Closure with Linear Expected Time. SIAM J. Comput. 7(2): 127-133(1978) BibTeX
Stephen Warshall: A Theorem on Boolean Matrices. J. ACM 9(1): 11-12(1962) BibTeX
Henry S. Warren Jr.: A Modification of Warshall's Algorithm for the Transitive Closure of Binary Relations. Commun. ACM 18(4): 218-220(1975) BibTeX

Referenced by

  1. Ismail H. Toroslu, Ghassan Z. Qadah: The Strong Partial Transitive-Closure Problem: Algorithms and Performance Evaluation. IEEE Trans. Knowl. Data Eng. 8(4): 617-629(1996)
  2. Shaul Dar, Raghu Ramakrishnan: A Performance Study of Transitive Closure Algorithms. SIGMOD Conference 1994: 454-465
  3. Shaul Dar, Rakesh Agrawal: Extending SQL with Generalized Transitive Closure Functionality. IEEE Trans. Knowl. Data Eng. 5(5): 799-812(1993)
  4. Håkan Jakobsson: On Tree-Based Techniques for Query Evaluation. PODS 1992: 380-392
  5. Shaul Dar, H. V. Jagadish: A Spanning Tree Transitive Closure Algorithm. ICDE 1992: 2-11
  6. Inderpal Singh Mumick, Hamid Pirahesh: Overbound and Right-Linear Queries. PODS 1991: 127-141
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:34:03 2009