Verifying partial orders

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Verifying partial orders

Full text

Pdf (447 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-first annual ACM symposium on Theory of computing table of contents

Seattle, Washington, United States

Pages: 367 - 374

Year of Publication: 1989

ISBN:0-89791-307-8

Authors

C. Kenyon-Mathieu	Princeton University, Department of Computer Science, Princeton, N. J.
V. King	University of Toronto, Department of Computer Science, Toronto, Canada M5S 1A4

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 6, Citation Count: 3

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/73007.73042 What is a DOI?

Warning: The download time has expired please click on the item to try again.

ABSTRACT

We present a randomized algorithm which uses O(n(log n)1/3) expected comparisons to verify that a given partial order holds on n elements from an unknown total order.

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.

	GYY	Ronald L. Graham , Andrew C. Yao , F. Frances Yao, Information Bounds Are Weak in the Shortest Distance Problem, Journal of the ACM (JACM), v.27 n.3, p.428-444, July 1980 [doi>10.1145/322203.322206]
	K	J. Koml6s. "Linear Verification for Spanning Trees," 25th Symposium on the Foundations of Computer Science, (1984), pp.201-206.
	Y	A. Yao, private communication.

CITED BY 3

	W. Goddard , V. King , L. Schulman, Optimal randomized algorithms for local sorting and set-maxima, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.45-53, May 13-17, 1990, Baltimore, Maryland, United States
	A. C.-C. Yao, Coherent functions and program checkers, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.84-94, May 13-17, 1990, Baltimore, Maryland, United States
	Seth Pettie , Vijaya Ramachandran, Randomized minimum spanning tree algorithms using exponentially fewer random bits, ACM Transactions on Algorithms (TALG), v.4 n.1, p.1-27, March 2008