0

I am searching for linear time complexity of MST. I am trying to proceed this using Fibonacci heap as its union and find minimum operation takes constant time. Is possibly there any link to reduce time complexity of MST? Please help.

Md. Hasanur Rahman
  • 11
  • 1
  • 3
  • Prim's algorithm? – kelalaka Oct 18 '18 at 12:02
  • actually I am trying to make linear time complexity for finding MST. I found this fibonacci heap whose Find-minimum() operation takes 0(1) time. Now I am interested whether there is a possiblity to improve time complexity using this operation or not? – Md. Hasanur Rahman Oct 19 '18 at 13:06
  • Prim with Fibonacci is O(E+V log V), But if the Graph is sparse can be O(E+log log V)] – kelalaka Oct 19 '18 at 13:10
  • Fibonacci Heaps are theoretically better than Binary Heaps. But their the constant factors hidden are very [high](https://stackoverflow.com/a/31196753/10311208) – kelalaka Oct 19 '18 at 21:13

0 Answers0