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
scroll top