Steiner tree problem

最小の頂点数を用いてグラフ上の二点をつなぐ問題は最短経路問題で解ける。

三点以上をつなぐ問題はminimum steiner tree problemといってNP困難な問題となる。