Transmission Network Design
Minimum Spanning Tree · Network Design
High-voltage transmission lines cost €1–€3M per kilometer, and redundant connections waste 5–12% of grid infrastructure budgets. Every major grid upgrade, a transmission planner must decide which substations to connect to ensure all nodes are reachable at minimum cabling cost. This is the Minimum Spanning Tree problem — solvable optimally in O(E log E) — extended with reliability constraints requiring Steiner tree or 2-edge-connected solutions.
Where This Decision Fits
Energy infrastructure planning chain — the highlighted step is what this page optimizes
The Problem
Building the minimum-cost connected transmission backbone
A regional grid operator manages 10 substations spread across a province. Between these substations, there are 25 potential transmission corridors, each with an estimated construction cost in millions of euros that reflects terrain difficulty, distance, and environmental permitting.
The objective is to build the minimum-cost set of transmission lines such that every substation is reachable from every other — forming a connected backbone network. The solution must use exactly |V| − 1 = 9 edges (for 10 nodes), ensuring connectivity without any redundant (and expensive) loops.
This is precisely the structure of the Minimum Spanning Tree (MST) problem: given an undirected, weighted, connected graph G = (V, E), find the spanning tree T of minimum total edge weight. Unlike many combinatorial optimization problems, MST is solvable in polynomial time with greedy algorithms.
subject to
Σ(i,j)∈E xij = |V| − 1 // exactly n-1 edges in a tree
Σ(i,j)∈E(S) xij ≤ |S| − 1 // no cycles (subtour elimination)
xij ∈ {0, 1} // binary edge selection
Where cij is the cost of corridor (i, j), xij indicates whether that corridor is built, and E(S) is the set of edges within subset S ⊆ V. The greedy approach avoids the exponential subtour constraints entirely.
See full MST theory and all algorithmsTry It Yourself
Select a scenario, choose an algorithm, and find the optimal transmission backbone
Transmission Network Solver
The Algorithms
Three classic greedy approaches to finding the minimum spanning tree
Kruskal's Algorithm
O(E log E)Sort all edges by weight, then iterate through them in ascending order. Add each edge to the tree if it does not form a cycle — checked efficiently with a Union-Find (disjoint set) data structure. Stops after exactly |V| − 1 edges are added.
Particularly well-suited for sparse graphs where E is much smaller than V². The sorting step dominates the runtime, making it O(E log E).
Prim's Algorithm
O(E log V)Start from an arbitrary vertex and grow the tree one edge at a time. At each step, add the cheapest edge connecting a vertex in the tree to a vertex outside it. Uses a priority queue (binary heap) to efficiently select the minimum-weight crossing edge.
Ideal for dense graphs. With a Fibonacci heap, complexity reduces to O(E + V log V), which is optimal for very dense networks.
Borůvka's Algorithm
O(E log V)Each connected component simultaneously selects its cheapest outgoing edge, then all selected edges are added, merging components. This process repeats until a single component (the MST) remains. At most O(log V) phases are needed since the number of components halves each round.
The oldest MST algorithm (1926) and naturally parallelizable — each component’s cheapest edge search is independent.
Complexity Comparison
- Kruskal's — O(E log E) ≈ O(E log V). Best for sparse graphs. Edge sorting dominates.
- Prim's — O(E log V) with binary heap. O(E + V log V) with Fibonacci heap.
- Borůvka's — O(E log V). At most log V phases, each scanning all edges.
- All three produce the same MST weight (guaranteed by the cut property).
Key References
Foundational papers and textbooks
- (1956). “On the shortest spanning subtree of a graph and the traveling salesman problem.” Proceedings of the AMS, 7(1), 48–50.
- (1957). “Shortest connection networks and some generalizations.” Bell System Technical Journal, 36(6), 1389–1401.
- (2009). “Introduction to Algorithms”, 3rd ed. MIT Press, Ch. 23 (Minimum Spanning Trees).
Need to optimize your grid infrastructure?
From transmission network design to generation scheduling and energy market optimization, mathematical modeling can transform grid planning decisions. Let’s discuss how Operations Research can work for you.