<blockquote>
<p>A Steiner tree is an undirected graph G=(V,E) consisting of a set of edges E and a set of nodes V. Given a subset T of V, a Steiner tree is a tree containing all the nodes in T. From the definition, it is clear that a Steiner tree is a <a href="/en/universal%20tree">universal tree</a> when T=V.</p>
</blockquote>
<pre><code>- The [Minimum Steiner Tree](/en/Minimum%20Steiner%20Tree) problem is a loosening of the [minimum area tree](/en/minimum%20area%20tree) problem so that not all vertices need to be connected.
</code></pre>
<ul>
<li><a href="/en/Dreyfus-Wagner">Dreyfus-Wagner</a><ul>
<li>Time complexity O(n 3^t + n^2 2^t + n^3)</li>
<li>Implementation <a href="http://www.prefield.com/algorithm/dp/steiner_tree.html">Spaghetti Source - Smallest Steiner Tree</a></li>
<li>The limit is about the required vertex t = 11</li>
</ul>
</li>
<li>When there are many required vertices and few optional vertices, there is a move to search all optional vertex selections<ul>
<li><a href="/en/PAST1L">PAST1L</a></li>
</ul>
</li>
</ul>
<hr>
<p>This page is auto-translated from <a href="https://scrapbox.io/nishio/%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%8A%E3%83%BC%E6%9C%A8">/nishio/シュタイナー木</a> using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at <a href="https://twitter.com/nishio_en">@nishio_en</a>. I&#39;m very happy to spread my thought to non-Japanese readers.</p>
