MaxSTs

A maximum spanning tree (MaxST) of a weighted undirected graph G=(V,E) with edge weights w is a spanning tree T⊆E that maximizes the sum of its edge weights ∑_{e∈T} w(e). If G is connected, a MaxST exists and is a single tree; if G is disconnected, one forms a maximum spanning forest by taking a MaxST in each connected component.

MaxSTs are analogous to minimum spanning trees but aim to maximize total weight. If all edge weights are distinct, the MaxST is unique; otherwise there may be several distinct MaxSTs.

Computing a MaxST can be done with standard MST algorithms adapted for maximization. Kruskal’s algorithm can be used by sorting edges in nonincreasing order and adding edges that do not form a cycle, continuing until a spanning tree (or forest) is formed. Prim’s algorithm can also be adapted by always extending the growing tree with the adjacent edge of maximum weight. The typical time complexity is O(m log n) with a priority queue and a disjoint-set data structure for Kruskal, or O(m log n) for Prim (dense graphs may use O(n^2) implementations as appropriate).

Relation to minimum spanning trees: negating all edge weights converts a MaxST problem to a standard MinST problem, and vice versa. Consequently, existing MST implementations can be used to compute MaxSTs by working with negated weights or by adjusting the edge-ordering to decreasing weights.

Applications of MaxSTs include network design scenarios where higher-weight edges reflect greater capacity, reliability, or bandwidth, and component-wise analysis in disconnected graphs where a maximum spanning forest is sought.