Minimum Connector Problem

Problem

Given a weighted graph $G$, the object is to find a minimum spanning tree for $G$.

Solution

There are two methods of solving this problem:

• Kruskal's Algorithm
• Prim's Algorithm

proved as:

• Kruskal's Algorithm produces Minimum Spanning Tree
• Prim's Algorithm produces Minimum Spanning Tree

Also see

The Maximum Connector Problem is effectively the same problem taken from a different direction.

Sources

• 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): minimum connector problem