A modification of Warshall's algorithm for the transitive closure of binary relations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A modification of Warshall's algorithm for the transitive closure of binary relations

Full text

Pdf (338 KB)

Source

Communications of the ACM archive
Volume 18 , Issue 4 (April 1975) table of contents

Pages: 218 - 220

Year of Publication: 1975

ISSN:0001-0782

Author

Henry S. Warren, Jr.

IBM Thomas J. Watson Research Center, Yorktown Heights, NY

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 20, Downloads (12 Months): 121, Citation Count: 18

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/360715.360746 What is a DOI?

ABSTRACT

An algorithm is given for computing the transitive closure of a binary relation that is represented by a Boolean matrix. The algorithm is similar to Warshall's although it executes faster for sparse matrices on most computers, particularly in a paging environment.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Stephen Warshall, A Theorem on Boolean Matrices, Journal of the ACM (JACM), v.9 n.1, p.11-12, Jan. 1962 [doi>10.1145/321105.321107]
	2	James J. Baker, A note on multiplying Boolean matrices, Communications of the ACM, v.5 n.2, p.102, Feb. 1962 [doi>10.1145/366792.366825]
	3	Martynyuk, V.V. Economic construction of transitive closure of binary relations. Zhurnal Vychisliteh2oi Matematiki i Matematicheskoi Fiziki 2 (July-Aug. 1962), 723-725.
	4	Thorelli, Lars-Erik. An algorithm for computing all paths in a graph. BIT 6 (1966), 347-349.
	5	Purdom, Paul, Jr. A transitive closure algorithm. BIT 10 (1970), 76-94.

CITED BY 18

	Yannis Ioannidis , Raghu Ramakrishnan , Linda Winger, Transitive closure algorithms based on graph traversal, ACM Transactions on Database Systems (TODS), v.18 n.3, p.512-576, Sept. 1993
	Jeffrey D. Ullman , Mihalis Yannakakis, The input/output complexity of transitive closure, ACM SIGMOD Record, v.19 n.2, p.44-53, Jun. 1990
	Håkan Jakobsson, Mixed-approach algorithms for transitive closure (extended abstract), Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.199-205, May 29-31, 1991, Denver, Colorado, United States
	Shaul Dar , Raghu Ramakrishnan, A performance study of transitive closure algorithms, ACM SIGMOD Record, v.23 n.2, p.454-465, June 1994
	Yun-Wu Huang , Ning Jing , Elke A. Rundensteiner, Path queries for transportation networks: dynamic reordering and sliding window paging techniques, Proceedings of the 4th ACM international workshop on Advances in geographic information systems, p.9-16, November 1996, Rockville, Maryland, United States
	H. V. Jagadish , Rakesh Agrawal , Linda Ness, A study of transitive closure as a recursion mechanism, ACM SIGMOD Record, v.16 n.3, p.331-344, Dec. 1987
	S. Ceri , G. Gottlob , L. Tanca, What You Always Wanted to Know About Datalog (And Never Dared to Ask), IEEE Transactions on Knowledge and Data Engineering, v.1 n.1, p.146-166, March 1989
	R. K. Shyamasundar, A note on the transitive closure of a boolean matrix, ACM SIGACT News, v.9 n.4, p.18-21, Winter 1978
	Rakesh Agrawal , Shaul Dar , H. V. Jagadish, Direct transitive closure algorithms: design and performance evaluation, ACM Transactions on Database Systems (TODS), v.15 n.3, p.427-458, Sept. 1990
	Mihalis Yannakakis, Graph-theoretic methods in database theory, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.230-242, April 02-04, 1990, Nashville, Tennessee, United States
	Jean Frédéric Myoupo , Anne Cécile Fabret, A Modular Systolic Linearization of the Warshall-Floyd Algorithm, IEEE Transactions on Parallel and Distributed Systems, v.7 n.5, p.449-455, May 1996
	Yangjun Chen , Donovan Cooke, On the transitive closure representation and adjustable compression, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France
	Yannis E. Ioannidis , Raghu Ramakrishnan, Efficient Transitive Closure Algorithms, Proceedings of the 14th International Conference on Very Large Data Bases, p.382-394, August 29-September 01, 1988
	Rakesh Agrawal , H. V. Jagadish, Direct Algorithms for Computing the Transitive Closure of Database Relations, Proceedings of the 13th International Conference on Very Large Data Bases, p.255-266, September 01-04, 1987
	Rakesh Agrawal , H. V. Jagadish, Hybrid Transitive Closure Algorithms, Proceedings of the 16th International Conference on Very Large Data Bases, p.326-334, August 13-16, 1990
	Quan Hoang Nguyen , Bernhard Scholz, Computing SSA Form with Matrices, Electronic Notes in Theoretical Computer Science (ENTCS), v.190 n.1, p.121-132, July, 2007
	Yangjun Chen, A new method for generating compressed representation of transitive closure, Proceedings of the 2008 C³S²E conference, May 12-13, 2008, Montreal, Quebec, Canada
	Yangjun Chen, General spanning trees and reachability query evaluation, Proceedings of the 2nd Canadian Conference on Computer Science and Software Engineering, May 19-21, 2009, Montreal, Quebec, Canada