Grab Bag Release: Minimum Spanning Trees

Okay, the last weeks have been full of work, my apologies for the delay. This weekend, I finally managed to finish my implementation of the algorithm for finding minimum spanning trees by Fredman and Tarjan, here we go.

Minimum Spanning Trees

Let G = (V, E) be a connected, undirected graph with |V| = n vertices and |E| = m edges (v, w) with non-negative edge weights c(v, w). A minimum spanning tree of G is a spanning tree of G with minimum total edge weight.

Minimum Spanning Tree

The algorithm presented in “Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms” by Michael L. Fredman and Robert Endre Tarjan in 1985 finds a minimum spanning tree of an input graph in O(m ß(m,n)), where

ß(m,n) = min{ i | log(i) n ≤ (m/n)}

and log(i) n is defined inductively by

  • log(0) n = n
  • log(i + 1) n = log log(i) n

Author: npruehs

Nick Pruehs is a Co-Founder of Slash Games, Hamburg. In 2009, he graduated as “Best Bachelor” in computer science at Kiel University. Two years later Nick finished his master’s degree in “Sound, Vision, Games” at Hamburg University of Applied Sciences, becoming the Lead Programmer of Daedalic Entertainment shortly after.

Questions? Comments? Suggestions? Your turn! :)