Expected Linear time Minimum Spanning Tree algorithm
-
04-11-2019 - |
Question
I am trying to understand the proposed "Randomized Linear-Time Algorithm to Find MST".
My findings: I have read and search almost every available resource( main paper, wiki, reports on paper, lecture on paper ) but not getting any clue regarding my confusion.
Question: In the original paper Section 3: The Algorithm "Step 2" says "In the contracted graph, choose a subgraph H by selecting each edge independently with probability 1/2."
If I have 6 vertexes with 14 edges. And if I choose 7 edges with probability 1/2 then there might be some isolated vertex. In that case, what will happen to that isolated vertex?
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange