0
$\begingroup$

I'm facing the following problem: Describe a distributed MST algorithm in time $O(n \log \log n)$

I've managed to think of the following,

  • Run GHS(Gallager, Humblet and Spira) algorithm, till there are $(n/(\log n))$ fragments.

This way I believe there's a small thing to do so the finding of roots to connect fragments, will take $\log \log n$.

Basically if there are $\log n$ fragments, searching for the root to connect to, is supposed to take $\log \log n$, because in usual case it takes $\log n$ for $n$ fragments. But I'm really not sure about this one

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Do you have a specific question? What specifically are you unsure about? What prevents you from being sure about your answer? We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. $\endgroup$ – D.W.♦ May 12 '17 at 16:51
  • $\begingroup$ I see, thank you for your comment, I would like to know the answer for the question, I guess that will be the best solution for me and future readers $\endgroup$ – Jeremy Shiklov May 12 '17 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.