Probabilistic recurrence relations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Probabilistic recurrence relations

Full text

Pdf (797 KB)

Source

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

New Orleans, Louisiana, United States

Pages: 190 - 197

Year of Publication: 1991

ISBN:0-89791-397-3

Author

Richard M. Karp

Univ. of California at Berkeley

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

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

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.

	DuSa	L.E. Dubins, L.J. Savage, How to Gamble If You Must, McGraw-Hill, New York, 1965.
	Fr	D. Freedman, "Another Note on the Borel- Cantelli Lemma and the Strong Law, with the Poisson Approximation as a By- Product," The Annals of Probability, Vol. 1, No. 6, pp. 910-925, 1973.
	KaUpWi	Richard M. Karp , Eli Upfal , Avi Wigderson, The complexity of parallel search, Journal of Computer and System Sciences, v.36 n.2, p.225-253, April 1988 [doi>10.1016/0022-0000(88)90027-X]
	Lu	Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.15 n.4, p.1036-1055, Nov. 1986 [doi>10.1137/0215074]
	MiRe	G.L. Miller and J.H. Reif, "Parallel Tree Contraction and its Application," Proc. 26th Annual IEEE Syrup. on Foundations of Computer Science, pp. 478-489, 1985.

CITED BY 12

	Irene Finocchi , Alessandro Panconesi , Riccardo Silvestri, Experimental analysis of simple, distributed vertex coloring algorithms, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.606-615, January 06-08, 2002, San Francisco, California
	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	David Karger , Serge Plotkin, Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.18-25, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Michał Hańćkowiak , Michał Karoński , Alessandro Panconesi, On the distributed complexity of computing maximal matchings, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.219-225, January 25-27, 1998, San Francisco, California, United States
	Ramesh Subramonian, Designing synchronous algorithms for asynchronous processors, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.189-198, June 29-July 01, 1992, San Diego, California, United States
	Michał Hańćkowiak , Michał Karoński , Alessandro Panconesi, A faster distributed algorithm for computing maximal matchings deterministically, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.219-228, May 04-06, 1999, Atlanta, Georgia, United States
	Philip Klein, On Gazit and Miller's parallel algorithm for planar separators: achieving greater efficiency through random sampling, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.43-49, June 30-July 02, 1993, Velen, Germany
	Mordecai J. Golin, Limit theorems for minimum-weight triangulations, other Euclidean functionals, and probabilistic recurrence relations, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.252-260, January 28-30, 1996, Atlanta, Georgia, United States
	David A. Grable , Alessandro Panconesi, Fast distributed algorithms for Brooks-Vizing colourings, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.473-480, January 25-27, 1998, San Francisco, California, United States
	Kequin Li, Probabilistic analysis of an approximation algorithm for maximum subset sum using recurrence relations, Proceedings of the 33rd annual on Southeast regional conference, March 17-18, 1995, Clemson, South Carolina
	Brian C. Dean, A simple expected running time analysis for randomized "divide and conquer" algorithms, Discrete Applied Mathematics, v.154 n.1, p.1-5, 1 January 2006
	Michail Argyriou , Vasilis Samoladas , Spyros Blanas, GRaSP: generalized range search in peer-to-peer networks, Proceedings of the 3rd international conference on Scalable information systems, June 04-06, 2008, Vico Equense, Italy