![[steiner-trees.jpeg|center|600]] ## Steiner Tree - You have a network $G$. - Find a subnetwork $S\subset G$, that entails a set of “terminal nodes”. - $S$ should have minimum sum of edge weights to connect these nodes, but other nodes from $G$ can be included to achieve this. >[!note:] >In a large network to brute-force all possibilities is not feasible. However we can approximate the Steiner tree by the minimum spanning tree. ## Minimum Spanning Tree - You have a network $G$. - Find a subnetwork $S \subset G$ that connects a fixed set of nodes. - $S$ should have minimum sum of edge weights to connect these nodes, and no additional nodes from $G$ can be included. >[!note:] >For both subnetwork types we need to assume that $G$ is fully connected. ## Approximation of Steiner Tree Since finding the exact Steiner Tree is computationally expensive, an approximation can be obtained using the following steps: *Step 1: Construct a Distance Matrix* - Record the distances between terminal nodes in a distance matrix $D$. - Each entry $D_{ij}$ represents the distance $d_{ij}$ between any terminal node $i$ and $j$. *Step 2: Build a Minimum Spanning Tree* - Use $D$ as the [[Network Types#^daa3e3|Adjacency Matrix]] of a new graph $A$. - Build a minimum spanning tree (”MST”) from it. *Step 3: Map the MST Back to the Original Graph* - If an edge $D_{ij}$ is an edge in the MST, find the shortest path between $i$ and $j$ in $A$. - Add all these edges to the Steiner tree approximation $S$. - Repeat this for all edges on the MST, until all terminal nodes are connected.