Finding minimum spanning forests in logarithmic time and linear work using random sampling | Zendy

Richard Cole | Zendy; Philip N. Klein | Zendy; Robert E. Tarjan | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Finding minimum spanning forests in logarithmic time and linear work using random sampling

Author(s) -

Richard Cole,

Philip N. Klein,

Robert E. Tarjan

Publication year - 1996

Publication title -

citeseer x (the pennsylvania state university)

Language(s) - English

Resource type - Conference proceedings

ISBN - 0-89791-809-6

DOI - 10.1145/237502.237563

Subject(s) - citation , computer science , logarithm , sampling (signal processing) , random access , library science , operations research , mathematics , telecommunications , operating system , mathematical analysis , detector

We describe a randomized CRCW PRAM algorithm thatfinds a minimum spanning forest of an n-vertex graph inO(log n) time and linear work. This shaves a factor of 2lognoff the best previous running time for a linear-work algorithm.The novelty in our approach is to divide the computationinto two phases, the first of which finds only a partialsolution. This idea has been used previously in parallel connectedcomponents algorithms.1 IntroductionWe describe the first work-optimal minimum...

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research