シュタイナー木（Steiner tree）とは、エッジの集合Eとノードの集合Vから成る無向グラフG=(V,E)において、Vの部分集合Tが与えられたとき、Tに含まれるノードすべてを含む木のことである。定義より、T=Vのとき、シュタイナー木は全域木となることは明らかである。
- 最小シュタイナー木問題は最小全域木問題をすべての頂点を繋がなくても良いように緩めた問題
- Dreyfus-Wagner
- 時間計算量 O(n 3^t + n^2 2^t + n^3)
- 実装 Spaghetti Source - 最小シュタイナー木
- 必須の頂点t = 11 程度が限界
- 必須の頂点が多く、オプショナルな頂点が少ない時、オプショナルな頂点の選択を全探索する手がある