A RANDOMIZED LINEAR-TIME ALGORITHM TO FIND MINIMUM SPANNING-TREES

Authors
KARGER DR KLEIN PN TARJAN RE
Citation
Dr. Karger et al., A RANDOMIZED LINEAR-TIME ALGORITHM TO FIND MINIMUM SPANNING-TREES, Journal of the Association for Computing Machinery, 42(2), 1995, pp. 321-328
Citations number
23
Categorie Soggetti
Computer Sciences","Computer Science Hardware & Architecture
Journal title
Journal of the Association for Computing Machinery
ISSN journal
00045411 → ACNP
Volume
42
Issue
2
Year of publication
1995
Pages
321 - 328
Database
ISI
SICI code
Abstract
We present a randomized linear-time algorithm to find a minimum spanni ng tree in a connected graph with edge weights. The algorithm uses ran dom sampling in combination with a recently discovered linear-time alg orithm for verifying a minimum spanning tree. Our computational model is a unit-cost random-access machine with the restriction that the onl y operations allowed on edge weights are binary comparisons.