シュタイナー木 - 西尾泰和の外部脳

シュタイナー木

シュタイナー木（Steiner tree）とは、エッジの集合Eとノードの集合Vから成る無向グラフG=(V,E)において、Vの部分集合Tが与えられたとき、Tに含まれるノードすべてを含む木のことである。定義より、T=Vのとき、シュタイナー木は全域木となることは明らかである。

最小シュタイナー木問題は最小全域木問題をすべての頂点を繋がなくても良いように緩めた問題

時間計算量 O(n 3^t + n^2 2^t + n^3)

必須の頂点t = 11 程度が限界

必須の頂点が多く、オプショナルな頂点が少ない時、オプショナルな頂点の選択を全探索する手がある