A new algorithm for computing transitive closures

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A new algorithm for computing transitive closures

Full text

Pdf (113 KB)

Source

Symposium on Applied Computing archive
Proceedings of the 2004 ACM symposium on Applied computing table of contents

Nicosia, Cyprus

SESSION: Information access and retrieval (IAR) table of contents

Pages: 1091 - 1092

Year of Publication: 2004

ISBN:1-58113-812-1

Author

Yangjun Chen

University of Winnipeg, Manitoba, Canada

Sponsor

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 24, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues peer to peer

Tools and Actions:	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/967900.968121 What is a DOI?

ABSTRACT

In this paper, we propose a new algorithm for computing transitive closures. It needs only O(e·b) time and O(n·b) space, where n represents the number of the nodes of a DAG (directed acyclic graph), e the numbers of the edges, and b the DAG's breadth.

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	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	2	J. Tarjan: Finding Optimum Branching, Networks, 7. 1977, pp. 25-35.