シュタイナーの木問題

3点A、B、Cのシュタイナー木（ A、B、C間に直接の接続はないことに注意）。シュタイナー点Sは三角形ABCのフェルマー点に位置する。

4点の解 - シュタイナー点はS ₁とS _2の2つあります

組合せ数学において、シュタイナー木問題、あるいはヤコブ・シュタイナーにちなんで名付けられた最小シュタイナー木問題は、組合せ最適化における一連の問題に対する包括的な用語である。シュタイナー木問題はさまざまな設定で定式化できるが、それらすべてにおいて、与えられたオブジェクト集合に対する最適な相互接続と、定義済みの目的関数が必要となる。よく知られた変種で、シュタイナー木問題という用語と同義に使われることが多いのは、グラフのシュタイナー木問題である。非負の辺重みと、通常ターミナルと呼ばれる頂点のサブセットを持つ無向グラフが与えられると、グラフのシュタイナー木問題では、すべてのターミナル（ただし追加の頂点が含まれる場合もある）を含み、辺の合計重みを最小にする最小重みのツリーが必要となる。さらによく知られている変種には、ユークリッドシュタイナー木問題や直線最小シュタイナー木問題がある。

グラフのシュタイナー木問題は、他の 2 つの有名な組み合わせ最適化問題である (非負の)最短経路問題と最小全域木問題の一般化として考えることができます。グラフのシュタイナー木問題にちょうど 2 つのターミナルが含まれる場合、この問題は最短経路を見つけることに帰着します。一方、すべての頂点がターミナルである場合、グラフのシュタイナー木問題は最小全域木と同等になります。ただし、非負の最短経路問題と最小全域木問題はどちらも多項式時間で解けるのに対し、シュタイナー木問題についてはそのような解法は知られていません。その決定変種である、与えられた入力に、ある与えられたしきい値よりも小さい重みの木があるかどうかを尋ねる問題はNP 完全であり、これは、与えられたグラフで最小重みの木を求める最適化変種がNP 困難であることを意味します。実際、この決定変種は、Karp の元々の 21 の NP 完全問題の中に含まれていました。グラフにおけるシュタイナー木問題は、回路レイアウトやネットワーク設計に応用されています。しかし、実際の応用では通常、様々なバリエーションが必要となるため、シュタイナー木問題の変種が数多く存在します。

シュタイナー木問題のほとんどのバージョンはNP困難ですが、いくつかの限定されたケースでは多項式時間で解くことができます。悲観的な最悪の計算量にもかかわらず、グラフ上のシュタイナー木問題や直線シュタイナー木問題など、いくつかのシュタイナー木問題の変種は、実際には、大規模な実世界の問題であっても効率的に解くことができます。^{[ 1 ] [ 2 ]}

ユークリッドシュタイナー木

N = 3～8辺の正多角形の頂点の最小シュタイナー木。N > 5の場合の最小ネットワーク長Lは、円周から1辺を引いた長さである。四角形はシュタイナー点を表す。

元の問題は、ユークリッド シュタイナーの木問題または幾何学的シュタイナーの木問題として知られる形式で表現されました。平面上のN個の点が与えられ、任意の 2 点が直接または他の点と線分によって相互接続されるように、合計長さが最小の線でそれらの点を接続することが目標です。

この問題はシュタイナーにちなんで名付けられているが、1811年にジョセフ・ディーツ・ジェルゴンヌによって次のように初めて提起された。「平面上の既知の位置に複数の都市がある。問題は、それらの都市を運河網で結ぶことであり、その全長は可能な限り短くすることである。」^{[ 3 ]}

接続線分は端点以外では交差せず、木を形成することが示されます。これが問題の名前の由来です。

N  = 3の場合の問題は長らく考察され、すぐに、N個の与えられた点すべてに接続する単一のハブを持ち、全長が最小となるスターネットワークを見つける問題へと拡張されました。しかしながら、シュタイナー木の問題はガウスの書簡で完全に定式化されましたが、初めて本格的に扱われたのは、1934年にヴォイチェフ・ヤルニークとミロシュ・ケスラーがチェコ語で書いた論文でした。この論文は長らく見過ごされていましたが、平面から高次元への問題の一般化を含め、後に他の研究者に帰せられる「シュタイナー木のほぼすべての一般的な性質」を既に含んでいました。^{[ 4 ]}

ユークリッドシュタイナー問題において、グラフに追加される点（シュタイナー点）は次数が3でなければならず、また、そのような点に接する3つの辺は3つの120度の角を形成しなければならない（フェルマー点を参照）。したがって、シュタイナー木が持つことができるシュタイナー点の最大数はN  − 2となる。ここで、Nは与えられた点の初期数である。（これらの特性はすべてジェルゴンヌによって既に確立されている。）

N = 3の場合、2 つのケースが考えられます。指定された点によって形成される三角形のすべての角度が 120 度未満である場合、解はフェルマー点に位置するシュタイナー点によって与えられます。それ以外の場合、解は 120 度以上の角度で交わる三角形の 2 辺によって与えられます。

一般のNに対して、ユークリッドシュタイナー木問題はNP困難であり、したがって多項式時間アルゴリズムを用いて最適解が見つかるかどうかは分かっていない。しかし、ユークリッドシュタイナー木には多項式時間近似スキーム（PTAS）があり、すなわち、多項式時間で近似最適解が見つかる可能性がある。^{[ 5 ]}ユークリッドシュタイナー木問題がNP完全であるかどうかは分かっていない。これは、複雑性クラスNPへの帰属が分かっていないためである。

直線シュタイナーツリー

直線シュタイナー木問題は、平面における幾何学的シュタイナー木問題の変形であり、ユークリッド距離が直線距離に置き換えられている。この問題は、電子設計自動化（EDA）の物理設計において発生する。VLSI回路では、配線の配線は、設計ルールによって垂直方向と水平方向のみに制約されることが多いため、直線シュタイナー木問題は、2つ以上の端子を持つネットの配線をモデル化するために用いることができる。^{[ 6 ]}

グラフと変種におけるシュタイナー木

シュタイナー木は、重み付きグラフの分野で広く研究されてきました。その原型は、おそらくグラフにおけるシュタイナー木問題 です。G  = ( V ,  E )を非負の辺重み c を持つ無向グラフとし、S  ⊆  V をターミナルと呼ばれる頂点のサブセットとします。シュタイナー木は、 Sを張るGの木です。この問題には 2 つのバージョンがあります。シュタイナー木に関連する最適化問題では、最小重みのシュタイナー木を見つけることがタスクです。決定問題では、辺重みは整数であり、合計重みが事前に定義された自然数kを超えないシュタイナー木が存在するかどうかを判定することがタスクです。決定問題は、Karp の 21 の NP 完全問題の 1 つです。したがって、最適化問題はNP 困難です。グラフにおけるシュタイナー木問題は、マルチキャストルーティング^{[ 8 ]}やバイオインフォマティクスなど、 ^{[ 7 ] [ 9 ]}

この問題の特殊なケースとして、Gが完全グラフで、各頂点v∈V が 計量空間内の点に対応し、各e∈E の 辺の重みw ( e )が空間内の距離に対応する場合が挙げられます。言い換えると、辺の重みは三角不等式を満たします。この変形は計量シュタイナー木問題として知られています。（非計量）シュタイナー木問題のインスタンスが与えられた場合、それを多項式時間で計量シュタイナー木問題の同等のインスタンスに変換できます。この変換では近似係数が保持されます。^{[ 10 ]}

ユークリッド版では PTAS が許容されるが、計量シュタイナー木問題はAPX 完全であることが知られている。つまり、P = NPでない限り、多項式時間で 1 に任意に近い近似比を達成することは不可能である。最小シュタイナー木を の係数以内に近似する多項式時間アルゴリズムが存在する。[ ^{11 ]しかし} 、係数以内で近似することはNP 困難である。^{[ 12 ]}距離が 1 と 2 のシュタイナー木問題の制限されたケースでは、1.25 近似アルゴリズムが知られている。^{[ 13 ]} Karpinski とAlexander Zelikovsky は、シュタイナー木問題の稠密なインスタンスに対して PTAS を構築した。^{[ 14 ]}${\displaystyle \ln(4)+\varepsilon \approx 1.386}$ ${\displaystyle 96/95\approx 1.0105}$

グラフ問題の特殊なケースである準二部グラフのシュタイナー木問題では、SにはGのすべての辺の少なくとも 1 つの端点が含まれている必要があります。

シュタイナー木問題は、高次元や様々な曲面上でも研究されてきました。球面、トーラス、射影平面、広い円錐、狭い円錐などにおいて、シュタイナー極小木を求めるアルゴリズムが見つかっています。^{[ 15 ]}

シュタイナー木問題の他の一般化としては、k辺連結シュタイナーネットワーク問題とk頂点連結シュタイナーネットワーク問題があり、これらの問題は連結グラフではなく、 k辺連結グラフまたはk頂点連結グラフを見つけることを目的とします。さらによく研究されている^{[ 16 ]}一般化として、生存可能ネットワーク設計問題（SNDP）があります。SNDPの問題は、各頂点ペアを、指定された数（場合によっては0）の辺または頂点が互いに素なパスで接続することです。

シュタイナー問題は、距離空間の一般的な設定や、おそらくは無限個の点に対しても述べられている。^{[ 17 ]}

シュタイナーツリーの近似

一般的なグラフ シュタイナー木問題は、1981 年に Kou らによって初めて発表されたように、末端の頂点によって誘導されるグラフのメトリック閉包のサブグラフの最小全域木を計算することによって近似できます。^{[ 18 ]}グラフのメトリック閉包は、各エッジが 内のノード間の最短経路距離によって重み付けされている完全なグラフです。このアルゴリズムは、重みが最適シュタイナー木の重みの係数以内である木を生成します。ここで、 は最適シュタイナー木の葉の数です。これは、最適シュタイナー木上の巡回セールスマン旅行を考えることによって証明できます。この近似解は、最初に全ペアの最短経路問題を解いてメトリック閉包を計算し、次に最小全域木問題を解くことで、多項式時間で計算できます。 ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle 2-2/t}$ ${\displaystyle t}$ ${\displaystyle O(|S||V|^{2})}$

グラフにおけるシュタイナー木を近似するもう一つの一般的なアルゴリズムは、1980年に高橋と松山によって発表されました^{[ 19 ]。}彼らの解法は、任意の頂点から開始し、木から最も近いまだ追加されていない頂点までの最短経路を繰り返し追加することで、シュタイナー木を段階的に構築します。このアルゴリズムにも実行時間があり、重みが最適値の範囲内にある木を生成します。 ${\displaystyle S}$ ${\displaystyle O(|S||V|^{2})}$ ${\displaystyle 2-2/|S|}$

1986年、Wuら^{[ 20 ]}は、全ペア最短経路の事前計算を回避することで、実行時間を劇的に改善しました。彼らは、最小全域木を計算するKruskalのアルゴリズムと同様のアプローチを採用し、素木の森から開始し、ダイクストラのアルゴリズムに似た幅優先探索を用いて複数の初期頂点から開始することで、同時にそれらを「成長」させています。探索中に現在の木に属していない頂点に遭遇すると、2つの木は1つに統合されます。このプロセスは、木が1つだけになるまで繰り返されます。このアルゴリズムは、優先キューを実装するためにヒープ（データ構造）を使用し、各頂点がどの木に属するかを追跡するために素集合データ構造を使用することで、Kouらのアルゴリズムのコスト比は改善されませんでしたが、実行時間を大幅に短縮しました。 ${\displaystyle |S|}$ ${\displaystyle O(|E|\log |V|)}$ ${\displaystyle 2-2/t}$

一連の論文で、最小シュタイナー木問題に対する近似アルゴリズムが提示され、近似比は近似比よりも改善された。この一連の論文は、2000年にRobinsとZelikovskyが提案したアルゴリズムで最高潮に達し、最小コスト終端全域木を反復的に改善することで近似比を1.55まで改善した。しかし、より最近では、Byrkaらが線形計画緩和法と反復ランダム化丸めと呼ばれる手法を用いて近似値を証明した。^{[ 11 ]}${\displaystyle 2-2/t}$ ${\displaystyle \ln(4)+\varepsilon \leq 1.39}$

シュタイナー木のパラメータ化された複雑さ

一般グラフシュタイナー木問題は、端末数をパラメータとする固定パラメータ で、ドレイファス・ワグナーアルゴリズムによって解けることが知られている。 ^{[ 21 ] [ 22 ]}ドレイファス・ワグナーアルゴリズムの実行時間は である。ここで、nはグラフの頂点数、Sは端末の集合である。より高速なアルゴリズムも存在し、任意の の時間で、あるいは重みが小さい場合には の時間で実行される。ここで、Wは任意の辺の最大重みである。^{[ 23 ] [ 24 ]}前述のアルゴリズムの欠点は、指数空間を使用することである。時間と の時間で実行される多項式空間アルゴリズムも存在する。^{[ 25 ] [ 26 ]}${\displaystyle 3^{|S|}{\text{poly}}(n)}$ ${\displaystyle c^{|S|}{\text{poly}}(n)}$ ${\displaystyle c>2}$ ${\displaystyle 2^{|S|}{\text{poly}}(n)W}$ ${\displaystyle 2^{|S|}{\text{poly}}(n)W}$ ${\displaystyle (7.97)^{|S|}{\text{poly}}(n)\log W}$

一般グラフシュタイナー木問題には、任意の （tは最適シュタイナー木の辺の数）に対して時間内に実行されるパラメータ化されたアルゴリズムが存在しないことが知られている。ただし、セットカバー問題には、ある（nとm は、それぞれセットカバー問題のインスタンスの要素数とセット数）に対して時間内に実行されるアルゴリズムが存在する。 ^{[ 27 ]}さらに、最適シュタイナー木の辺の数でパラメータ化された （すべての辺の重みが 1 である）場合でも、この問題は多項式カーネルを許容しないことが知られている。^{[ 28 ]}${\displaystyle 2^{\epsilon t}{\text{poly}}(n)}$ ${\displaystyle \epsilon <1}$ ${\displaystyle 2^{\epsilon n}{\text{poly}}(m)}$ ${\displaystyle \epsilon <1}$ ${\displaystyle {\textsf {coNP}}\subseteq {\textsf {NP/poly}}}$

シュタイナー木のパラメータ化された近似

グラフシュタイナー木問題は、端末の数でパラメータ化されない限り多項式カーネルを許容しないが、多項式サイズの近似カーネル化スキーム（PSAKS）を許容する。任意のグラフに対して、多項式サイズのカーネルを計算することが可能であり、これにより解の品質が1要素だけ低下する。^{[ 29 ]}${\displaystyle {\textsf {coNP}}\subseteq {\textsf {NP/poly}}}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle 1+\varepsilon }$

グラフシュタイナー木問題を、最適解における非終端点（シュタイナー頂点）の数pでパラメータ化すると、この問題はW[1] 困難となる（前述の終端点の数によるパラメータ化とは対照的である）。同時に、この問題はAPX 完全であり、したがってP = NPでない限りPTAS は成立しない。しかし、任意の に対して -近似値を時間内に計算するパラメータ化された近似スキームが存在する。 ^{[ 30 ]}また、このパラメータ化には PSAKS も存在する。^{[ 30 ]}${\displaystyle \varepsilon >0}$ ${\displaystyle (1+\varepsilon )}$ ${\displaystyle 2^{O(p^{2}/\varepsilon ^{4})}n^{O(1)}}$

シュタイナー比

シュタイナー比は、ユークリッド平面上の点の集合に対する最小全域木と最小シュタイナー木の全長の比の最大値である。 ^{[ 31 ]}

ユークリッドシュタイナー木問題におけるギルバート・ポラック予想は、シュタイナー比が であるというものです。これは、正三角形の3点と、その2辺を用いる全域木と、それらの点を三角形の重心で結ぶシュタイナー木によって得られる比です。^{[ 32 ]}以前から証明が主張されているにもかかわらず、この予想は未だ未解決です。^{[ 33 ]}この問題の最も広く受け入れられている上限は、 Chung & Graham (1985)による1.2134です。 ${\displaystyle {\tfrac {2}{\sqrt {3}}}\approx 1.1547}$

直線シュタイナー木問題では、シュタイナー比はちょうど であり、これは正方形の3辺を使用する全域木と、正方形の中心を通る点を結ぶシュタイナー木を持つ正方形内の4つの点によって達成される比である。^{[ 34 ]}より正確には、距離の場合、正方形は座標軸に対して だけ傾けられるべきであり、距離の場合、正方形は軸に沿っているべきである。 ${\displaystyle {\tfrac {3}{2}}}$ ${\displaystyle L_{1}}$ ${\displaystyle 45^{\circ }}$ ${\displaystyle L_{\infty }}$

参照

• 不透明森林問題
• 巡回セールスマン問題

注記

1. Rehfeldt & Koch (2023) .
2. Juhl et al. (2018) .
3. マーカス・ブラジル、ロナルド・L・グラハム、ドリーン・A・トーマス、マーティン・ザカリアセン、「ユークリッドシュタイナー木問題の歴史について」、 JSTOR  24569605
4. ベルンハルト、コルテ; Nešetřil、Jaroslav (2001)、「組み合わせ最適化における Vojtěch Jarnik の研究」、離散数学、235 ( 1–3 ): 1–17、doi : 10.1016/S0012-365X(00)00256-9、hdl : 10338.dmlcz/500662、MR  1829832。
5. クレセンツィ他（2000） .
6. シェルワニ（1993）、228ページ。
7. Ljubić, Ivana (2021). 「シュタイナー木の解読：最近の進歩、課題、そして展望」 . Networks . 77 (2): 177– 204. doi : 10.1002/net.22005 . ISSN 1097-0037 . S2CID 229458488 .  
8. Novak, Roman; Rugelj, Joz̆e; Kandus, Gorazd (2001年10月1日). 「ポイントツーポイントネットワークにおける分散マルチキャストルーティングに関する注記」 . Computers & Operations Research . 28 (12): 1149– 1164. doi : 10.1016/S0305-0548(00)00029-0 . ISSN 0305-0548 . 
9. Klimm, Florian; Toledo, Enrique M.; Monfeuga, Thomas; Zhang, Fang; Deane, Charlotte M.; Reinert, Gesine (2020年11月2日). 「単一細胞RNAシーケンシングデータとタンパク質間相互作用ネットワークの統合による機能モジュール検出」 . BMC Genomics . 21 (1): 756. doi : 10.1186/s12864-020-07144-2 . ISSN 1471-2164 . PMC 7607865. PMID 33138772 .   
10. ヴァジラニ (2003)、27–28 ページ。
11. Byrka et al. (2010) .
12. Chlebík & Chlebíková (2008)。
13. バーマン、カルピンスキー、ゼリコフスキー（2009）。
14. カルピンスキー＆ゼリコフスキー（1998）。
15. スミス＆ウィンター（1995）、361ページ。
16. Kerivin, Hervé; Mahjoub, A. Ridha (2005). 「生き残りやすいネットワークの設計：概観」 . Networks . 46 (1): 1– 21. doi : 10.1002/net.20072 . ISSN 0028-3045 . S2CID 8165318 .  
17. パオリーニ＆ステパノフ（2012） .
18. コウ、マーコウスキー、バーマン (1981)。
19. 高橋＆松山 (1980)。
20. ウー、ウィドマイヤー、ウォン (1986)。
21. ドレフュス＆ワグナー（1971年）。
22. レビン（1971年）。
23. Fuchs et al. (2007) .
24. Björklund et al. (2007) .
25. ロクシュタノフ＆ネデルロフ (2010) .
26. Fomin et al. (2015) .
27. Cygan et al. (2016) .
28. ドム、ロクシュタノフ、サウラブ (2014)。
29. ロクシュタノフ, ダニエル; パノラン, ファハド; ラマヌジャン, MS; サウラブ, サケト (2017年6月19日). 「Lossy kernelization」 .第49回ACM SIGACT計算理論シンポジウム議事録(PDF) . STOC 2017. ニューヨーク: Association for Computing Machinery. pp.  224– 237. doi : 10.1145/3055399.3055456 . ISBN 978-1-4503-4528-6. S2CID  14599219 .
30. ドヴォルザーク、パーヴェル;フェルドマン、アンドレアス E.クノップ、ドゥシャン。マサジーク、トマーシュ。トゥファール、トマーシュ。ヴェセリー、パベル（2021年1月1日）。「少数のシュタイナー頂点を持つシュタイナー ツリーのパラメータ化された近似スキーム」。離散数学に関する SIAM ジャーナル。35 (1): 546–574 . arXiv : 1710.00668。土井：10.1137/18M1209489。ISSN 0895-4801。S2CID 3581913。  
31. ガンリー（2004年）。
32. ジーナ・コラタ 1990年10月30日 古いパズルの解決法：近道はどれくらい短いのか？ニューヨーク・タイムズ
33. イワノフ＆トゥジリン（2012） .
34. ファン（1976）。

参考文献

• ピオトル・バーマン、マレク・カルピンスキー、アレクサンダー・ゼリコフスキー (2009). 「距離1と2のシュタイナー木問題に対する1.25近似アルゴリズム」.アルゴリズムとデータ構造：第11回国際シンポジウム、WADS 2009、カナダ、バンフ、2009年8月21日～23日、議事録. コンピュータサイエンス講義ノート. 第5664巻. pp.  86～ 97. arXiv : 0810.1851 . doi : 10.1007/978-3-642-03367-4_8 . ISBN 978-3-642-03366-7。
• バーン, マーシャル W.;グラハム, ロナルド L. (1989). 「最短ネットワーク問題」. Scientific American . 260 (1): 84–89 . Bibcode : 1989SciAm.260a..84B . doi : 10.1038/scientificamerican0189-84 .
• Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko (2007). 「Fourier Meets Möbius: Fast Subset Convolution」.第39回ACM計算理論シンポジウム論文集. pp.  67– 74. arXiv : cs/0611101 . doi : 10.1145/1250790.1250801 . ISBN 978-1-59593-631-8。
• Byrka, J.; Grandoni, F.; Rothvoß, T.; Sanita, L. (2010). 「シュタイナー木に対する改良LPベース近似法」.第42回ACM計算理論シンポジウム論文集. pp.  583– 592. CiteSeerX  10.1.1.177.3565 . doi : 10.1145/1806689.1806769 . ISBN 978-1-4503-0050-6。
• フレビク、ミロスラフ。Chlebíková、Janka (2008)。「グラフ上のシュタイナー木問題: 非近似性の結果」。理論的なコンピューターサイエンス。406 (3): 207–214。土井: 10.1016/j.tcs.2008.06.046。
• Chung, FRK ; Graham, RL (1985). 「ユークリッドシュタイナー極小木の新しい境界」.離散幾何学と凸性 (ニューヨーク, 1982) . Annals of the New York Academy of Science. Vol. 440. ニューヨーク: New York Academy of Science. pp.  328– 346. Bibcode : 1985NYASA.440..328C . doi : 10.1111/j.1749-6632.1985.tb14564.x . MR  0809217 .
• Cieslik, Dietmar (1998). Steiner Minimal Trees . Springer. p. 319. ISBN 0-7923-4983-0。
• クレッシェンツィ、ピエルルイジ。カン、ヴィゴ。ハルドルソン、マグナス。Karpinski, マレク;ウーギンガー、ゲルハルト(2000)。「最小幾何学的シュタイナー木」。NP 最適化問題の概要。
• サイガン、マレック。デル、ホルガー。ロクシュタノフ、ダニエル。マルクス、ダニエル。ネーダーロフ、ジェスパー。岡本 良雄パトゥリ、ラマモハン。サウラブ、サケット。ワールストロム、マグナス (2016)。「CNF-SAT と同じくらい難しい問題について」。アルゴリズムに関する ACM トランザクション。12 (3): 41:1–41:24。arXiv : 1112.2275。土井：10.1145/2925416。S2CID  7320634。
• Dom, Michael; Lokshtanov, Daniel; Saurabh, Saket (2014). 「色とIDによるカーネル化の下限値」. ACM Transactions on Algorithms . 11 (2): 13:1–13:20. doi : 10.1145/2650261 . S2CID  13570734 .
• Dreyfus, SE; Wagner, RA (1971). 「グラフにおけるシュタイナー問題」. Networks . 1 (3): 195– 207. doi : 10.1002/net.3230010302 .
• Fomin, Fedor V.; Kaski, Petteri; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket (2015). 「シュタイナー木のためのパラメータ化された単一指数時間多項式空間アルゴリズム」.オートマトン、言語、プログラミング – 第42回国際コロキウム、ICALP 2015、議事録、パートI.コンピュータサイエンス講義ノート. 第9134巻. pp.  494– 505. doi : 10.1007/978-3-662-47672-7_40 . hdl : 1956/23311 . ISBN 978-3-662-47671-0。
• フックス、ベンジャミン。カーン、ウォルター。メル、ダニエル。リヒター、ステファン。ロスマニス、ピーター。王新恵 (2007)。「最小シュタイナー木のための動的プログラミング」(PDF)。コンピューティング システムの理論。41 (3): 493–500。土井: 10.1007/s00224-007-1324-4。S2CID  7478978。
• Ganley, Joseph L. (2004). 「シュタイナー比」. Black, Paul E. (編). 『アルゴリズムとデータ構造の辞書』 . 米国国立標準技術研究所. 2012年5月24日閲覧.
• ゲイリー、マイケル・R.、ジョンソン、デイビッド・S. (1979). 『コンピュータとイントラクタビリティ：NP完全性理論へのガイド』 数学科学シリーズ（第1版） ニューヨーク：WHフリーマン・アンド・カンパニーISBN 9780716710455. MR  0519066 . OCLC  247570676 .、pp. 208-209、問題 ND12 および ND13。
• Hwang, FK (1976). 「直線距離を持つシュタイナー極小木について」. SIAM応用数学ジャーナル. 30 (1): 104– 114. doi : 10.1137/0130013 .
• Hwang, FK; Richards, DS; Winter, P. (1992).シュタイナー木問題. Annals of Discrete Mathematics. 第53巻. North-Holland : Elsevier . ISBN 0-444-89098-X。
• イワノフ、アレクサンダー、トゥジリン、アレクセイ（1994）『極小ネットワーク：シュタイナー問題とその一般化』NW、フロリダ州ボカラトン：CRCプレス、ISBN 978-0-8493-8642-8。
• イワノフ、アレクサンダー；トゥジリン、アレクセイ（2000）．一次元変分問題への分岐解法．シンガポール・ニュージャージー・ロンドン・香港：ワールドサイエンティフィック．ISBN 978-981-02-4060-8。
• イワノフ、アレクサンダー、トゥジリン、アレクセイ (2003). 『エクストリームネットワーク理論』（ロシア語）. モスクワ・イジェフスク：コンピュータ調査研究所. ISBN 5-93972-292-X。
• イワノフ, アレクサンダー; トゥジリン, アレクセイ (2012). 「シュタイナー比ギルバート・ポラック予想は依然として未解決：明確化声明」. Algorithmica . 62 ( 1–2 ): 630–632 . doi : 10.1007/s00453-011-9508-3 . S2CID  7486839 .
• イワノフ, アレクサンダー; トゥジリン, アレクセイ (2015). 「分岐被覆とシュタイナー比」.国際オペレーションズ・リサーチ論文集. 23 (5): 875– 882. arXiv : 1412.5433 . doi : 10.1111/itor.12182 . S2CID  3386263 .
• Juhl, D.; Warme, DM; Winter, P.; Zachariasen, M. (2018年1月). 「平面上のシュタイナー木を計算するためのGeoSteinerソフトウェアパッケージ：最新の計算研究」 .数理計画法計算. 10 (4): 487– 532. doi : 10.1007/s12532-018-0135-8 . S2CID  255616114 .
• Rehfeldt, D.; Koch, T. (2023年2月). 「シュタイナー木に対する含意、衝突、および縮約」 .数理計画. 197 (2): 903– 966. doi : 10.1007/s10107-021-01757-5 . S2CID  231842568 .
• カルピンスキー、マレク；ゼリコフスキー、アレクサンダー (1998). 「被覆問題の稠密ケースの近似」 . DIMACSワークショップ「ネットワーク設計：接続性と施設の位置」議事録. 離散数学と理論計算機科学におけるDIMACSシリーズ. 第40巻. アメリカ数学会. pp.  169– 178.
• Korte, Bernhard ; Vygen, Jens (2006). 「セクション20.1」.組合せ最適化：理論とアルゴリズム（第3版）. Springer . ISBN 3-540-25684-9。
• コウ、Ｌ．マーコウスキー、G.バーマン、L. (1981 年 6 月 1 日) 「シュタイナー木の高速アルゴリズム」。アクタ・インフォマティカ。15 (2): 141–145。土井: 10.1007/BF00288961。S2CID  21057232。
• レビン, A. Yu. (1971). 「グラフ頂点群の最短接続を求めるアルゴリズム」.ソビエト数学Doklady . 12 : 1477–1481 .
• ロクシュタノフ, ダニエル; ネデルロフ, イェスパー (2010). 「代数化による空間の節約」.第42回ACM計算理論シンポジウム論文集. pp.  321– 330. doi : 10.1145/1806689.1806735 . ISBN 978-1-4503-0050-6。
• Paolini, E.; Stepanov, E. (2012). 「シュタイナー問題の存在性と正則性の結果」(PDF) . Calc. Var. Partial Diff. Equations . 46 ( 3–4 ): 837– 860. doi : 10.1007/s00526-012-0505-4 . hdl : 2158/600141 . S2CID  55793499 .
• ロビンズ、ガブリエル；ゼリコフスキー、アレクサンダー (2000). 「グラフにおけるシュタイナー木近似の改良」 .第11回ACM-SIAM離散アルゴリズムシンポジウム (SODA '00) 議事録. 米国ペンシルベニア州フィラデルフィア：応用数学協会. pp.  770–779 . ISBN 0-89871-453-2。
• シェルワニ、ナビード・A. (1993). VLSI物理設計自動化のためのアルゴリズム. Kluwer Academic Publishers. ISBN 9781475722192。
• Smith, JM; Winter, P. (1995). 「計算幾何学と位相ネットワーク設計」. Du, Ding-Zhu; Hwang, Fr​​ank (編).ユークリッド幾何学におけるコンピューティング. コンピューティングに関する講義ノートシリーズ. 第4巻 (第2版). ニュージャージー州リバーエッジ: World Scientific Publishing Co. pp.  351– 451. ISBN 981-02-1876-1。
• 高橋宏光・松山明 (1980). 「グラフにおけるシュタイナー問題の近似解」.数学. 24 (6): 573–577 .
• ヴァジラニ、ビジェイ V. (2003)。近似アルゴリズム。ベルリン：シュプリンガー。ISBN 3-540-65367-8。
• Wu, Bang Ye; Chao, Kun-Mao (2004). 「第7章スパニングツリーと最適化問題」 . Chapman & Hall/CRC. ISBN 1-58488-436-3。
• Wu, YF; Widmayer, P.; Wong, CK (1986年5月). 「グラフにおけるシュタイナー問題に対する高速近似アルゴリズム」. Acta Informatica . 23 (2): 223– 229. doi : 10.1007/bf00289500 . S2CID  7772232 .

外部リンク

• GeoSteiner (ユークリッドおよび直線シュタイナー木問題を解くソフトウェア。ソースコードが利用可能、非商用利用は無料)
• SCIP-Jack (グラフおよび 14 種類の変種 (例: 賞金獲得型シュタイナー木問題) のシュタイナー木問題を解くソフトウェア。非商用利用は無料)
• 三角形のシュタイナー頂点 (フェルマー点)、三角形の頂点からの距離、および相対的な頂点の重みを見つけるための Fortran サブルーチン。
• Phylomurka（グラフ上の小規模シュタイナー木問題のソルバー）
• https://www.youtube.com/watch?v=PI6rAOWu-Og（動画：水と石鹸でシュタイナーの木問題を解く）
• Noormohammadpour, Mohammad; Raghavendra, Cauligi S.; Rao, Sriram; Kandula, Srikanth (2017)、「シュタイナー木を用いたバルクデータ転送の平均完了時間の最小化」、DCCast: データセンター間の効率的なポイントツーマルチポイント転送、USENIX Association、arXiv : 1707.02096
• Hazewinkel, M. (2001) [1994]、「シュタイナー木問題」、数学百科事典、EMSプレス
• M. ハウプトマン、M. カルピンスキー (2013): シュタイナーツリー問題集