965 views
1 votes
1 votes
For a sparse graph $G=(V,E)$ where $|E|=\Theta (V)$ is the implementation of Prim’s algorithm with a Fibonacci heap asymptotically faster than the binary-heap implementation? What about for a dense graph, where $|E|=\Theta (V)^{2}$? How must the sizes $|E|$ and $|V|$ be related for the Fibonacci-heap implementation to be asymptotically faster than the binary-heap implementation?

__________________________________________________________________________

Plz tell me difference between Sparse and Dense graph here? How Dense graph implemented and how it make difference for this question

Please log in or register to answer this question.

Related questions

3 votes
3 votes
1 answer
1
Pooja Palod asked Oct 15, 2015
2,990 views
Suppose that edge weights are uniformly distributed over half open interval $[0,1)$. Which algorithm kruskal's or prim's can make you run faster?