Bottleneck Steiner Tree Problem

• INSTANCE: Graph $G=(V,E)$ , edge costs $c: E \rightarrow \mathbb{R}^+$ , set of terminals $S\subseteq V$ .
• SOLUTION: A tree $T=(V_{T}, E_{T})$ in $G$ such that $S \subseteq V_{T} \subseteq V$ , $E_{T} \subseteq E$ .
• COST FUNCTION: $$\max_{e \in E_{T}}c(e)$$
• OBJECTIVE: Minimize.
• Approx.: Can be solved exactly in polynomial time [42][99][41].