Maximum Connector Problem

Problem

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

Solution

This is a variant of the Minimum Connector Problem.

It can be solved by either:

• Kruskal's Algorithm;

• Prim's Algorithm,

with appropriate modifications so as to choose the largest weight at each stage.