maxST

MaxST, short for maximum spanning tree, is a concept in graph theory. For a weighted undirected graph G = (V, E) with edge weights w: E → R, a maximum spanning tree is a spanning tree that maximizes the total weight of its edges. If the graph is connected, such a tree exists; if not, a maximum spanning forest consists of the maximum spanning trees of each connected component. All maximum spanning trees have the same number of edges, namely |V| − 1, and may not be unique when edge weights are tied.

Properties include that a maxST is acyclic and connects all vertices it spans. By maximizing the sum of edge weights, a maxST tends to include stronger or heavier edges while maintaining connectivity. When edge weights are distinct, the maxST is unique; with ties, multiple maximum spanning trees can exist.

Computation can be performed with standard MST algorithms adapted to prefer heavier edges. Prim’s algorithm can be directed to select the maximum-weight edge at each step, while Kruskal’s algorithm processes edges in decreasing order and adds an edge if it does not form a cycle. With a union–find data structure, Kruskal runs in O(E log V); Prim with a binary heap runs in O(E log V), and in dense graphs some implementations achieve O(V^2). Alternatively, negating all weights and applying a minimum spanning tree algorithm yields a maxST.

Applications include providing a compact representation of strong connections in a graph, design and reliability analysis of networks, and certain data analysis and clustering tasks where preserving high-weight links is desirable. The maxST is related to the minimum spanning tree, which minimizes total edge weight, and many algorithms are shared between the two problems.