Abstract
This note gives a short proof of a sampling lemma used by Karger, Klein, and Tarjan in the analysis of their randomized linear-time algorithm for minimum spanning trees.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 303-304 |
| Number of pages | 2 |
| Journal | Information Processing Letters |
| Volume | 67 |
| Issue number | 6 |
| DOIs | |
| State | Published - Sep 30 1998 |
| Externally published | Yes |
Keywords
- Algorithms
- Backwards analysis
- Minimum spanning trees
- Randomized algorithms
ASJC Scopus subject areas
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications