CSE521 - Links and Resources

CSE Home

Course Home Page

About Us

Search

Contact Info

Randomized Graph Algorithms

• A New Approach to the Minimum Cut Problem, Karger and Stein, 1996.
• A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees, Karger, Klein, and Tarjan, 1995.
• Randomization in Graph Optimization Problems: A Survey, David Karger, 1998.
• David Karger's thesis: Random Sampling in Graph Optimization Problems.
• David Karger's homepage and publications.
• Backwards Analysis of Randomized Geometric Algorithms, Raimund Seidel, 1992
• Size-Estimation Framework with Applications to Transitive Closure and Reachability, Edith Cohen, 1994.

	Department of Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to gidon]