Editing Steiner tree problem

{{Short description|On short connecting networks with added vertices}}
{{Use dmy dates|date=May 2022}}
[[File:Steiner 3 points.svg|thumb|Steiner tree for three points {{mvar|A}}, {{mvar|B}}, and {{mvar|C}} (note there are no direct connections between {{mvar|A}}, {{mvar|B}}, {{mvar|C}}). The Steiner point {{mvar|S}} is located at the [[Fermat point]] of the [[triangle]] {{mvar|ABC}}.]]
[[File:Steiner 4 points.svg|thumb|Solution for four points—there are two Steiner points, {{math|''S''{{sub|1}}}} and {{math|''S''{{sub|2}}}}]]

In [[combinatorial mathematics]], the '''Steiner tree problem''', or '''minimum Steiner tree problem''', named after [[Jakob Steiner]], is an [[umbrella term]] for a class of problems in [[combinatorial optimization]]. While Steiner tree problems may be formulated in a number of settings, they all require an optimal interconnect for a given set of objects and a predefined [[objective function]].  One well-known variant, which is often used synonymously with the term Steiner tree problem, is the '''Steiner tree problem in graphs'''. Given an [[undirected graph]] with non-negative edge weights and a subset of vertices, usually referred to as '''terminals,''' the Steiner tree problem in graphs requires a [[Tree (graph theory)|tree]] of minimum weight that contains all terminals (but may include additional vertices) and minimizes the total weight of its edges. Further well-known variants are the ''Euclidean Steiner tree problem'' and the ''[[Rectilinear Steiner tree|rectilinear minimum Steiner tree problem]]''.

The Steiner tree problem in graphs can be seen as a generalization of two other famous combinatorial optimization problems: the (non-negative) [[shortest path problem]] and the [[Minimum spanning tree|minimum spanning tree problem]]. If a Steiner tree problem in graphs contains exactly two terminals, it reduces to finding the shortest path. If, on the other hand, all vertices are terminals, the Steiner tree problem in graphs is equivalent to the minimum spanning tree. However, while both the non-negative shortest path and the minimum spanning tree problem are solvable in [[polynomial time]], no such solution is known for the Steiner tree problem. Its [[Decision problem|decision variant]], asking whether a given input has a tree of weight less than some given threshold, is [[NP-complete]], which implies that the optimization variant, asking for the minimum-weight tree in a given graph, is [[NP-hardness|NP-hard]]. In fact, the decision variant was among [[Karp's 21 NP-complete problems|Karp's original 21 NP-complete problems]]. The Steiner tree problem in graphs has applications in [[Electrical network|circuit]] layout or [[network design]]. However, practical applications usually require variations, giving rise to a multitude of Steiner tree problem variants.

Most versions of the Steiner tree problem are NP-hard, but some restricted cases can be solved in polynomial time. Despite the pessimistic [[worst-case complexity]], several Steiner tree problem variants, including the Steiner tree problem in graphs and the rectilinear Steiner tree problem, can be solved efficiently in practice, even for large-scale real-world problems.{{sfnp|Rehfeldt|Koch|2023}}{{sfnp|Juhl|Warme|Winter |Zachariasen|2018}}

==Euclidean Steiner tree==
{{regular_polygon_minimum_spanning_tree.svg}}
The original problem was stated in the form that has become known as the '''Euclidean Steiner tree problem''' or '''geometric Steiner tree problem''': Given ''N'' points in the [[Plane (geometry)|plane]], the goal is to connect them by lines of minimum total length in such a way that any two points may be interconnected by [[line segment]]s either directly or via other [[Point (geometry)|points]] and line segments.

While the problem is named after Steiner, it has first been posed in 1811 by [[Joseph Diez Gergonne]] in the following form: "A number of cities are located at known locations on a plane; the problem is to link them together by a system of canals whose total length is as small as possible".<ref>Marcus Brazil, Ronald L. Graham, Doreen A. Thomas and Martin Zachariasen, "On the history of the Euclidean Steiner tree problem", {{JSTOR|24569605}}</ref>

It may be shown that the connecting line segments do not intersect each other except at the endpoints and form a tree, hence the name of the problem.

The problem for {{math|1=''N''&nbsp;=&nbsp;3}} has long been considered, and quickly extended to the problem of finding a [[star (graph theory)|star network]] with a single hub connecting to all of the ''N'' given points, of minimum total length.
However, although the full Steiner tree problem was formulated in a letter by [[Carl Friedrich Gauss|Gauss]], its first serious treatment was in a 1934 paper written in Czech by [[Vojtěch Jarník]] and {{ill|Miloš Kössler|cs}}. This paper was long overlooked, but it already contains "virtually all general properties of Steiner trees" later attributed to other researchers, including the generalization of the problem from the plane to higher dimensions.<ref>{{citation
 | last1 = Korte | first1 = Bernhard | author1-link = Bernhard Korte
 | last2 = Nešetřil | first2 = Jaroslav | author2-link = Jaroslav Nešetřil
 | doi = 10.1016/S0012-365X(00)00256-9
 | issue = 1–3
 | journal = Discrete Mathematics
 | mr = 1829832
 | pages = 1–17
 | title = Vojtěch Jarnik's work in combinatorial optimization
 | volume = 235
 | year = 2001| hdl = 10338.dmlcz/500662
 | hdl-access = free
 }}.</ref>

For the Euclidean Steiner problem, points added to the graph ([[Steiner point (computational geometry)|Steiner points]]) must have a [[Degree (graph theory)|degree]] of three, and the three edges incident to such a point must form three 120 degree angles (see [[Fermat point]]). It follows that the maximum number of Steiner points that a Steiner tree can have is {{math|1=''N''&nbsp;&minus;&nbsp;2}}, where ''N'' is the initial number of given points. (all these properties were established already by Gergonne.)

For ''N'' = 3 there are two possible cases: if the triangle formed by the given points has all angles which are less than 120 degrees, the solution is given by a Steiner point located at the [[Fermat point]]; otherwise the solution is given by the two sides of the triangle which meet on the angle with 120 or more degrees.

For general ''N'', the Euclidean Steiner tree problem is [[NP-hard]], and hence it is not known whether an [[Optimization problem|optimal solution]] can be found by using a [[polynomial-time algorithm]]. However, there is a [[polynomial-time approximation scheme]] (PTAS) for Euclidean Steiner trees, i.e., a ''near-optimal'' solution can be found in polynomial time.{{sfnp|Crescenzi|Kann|Halldórsson|Karpinski|2000}} It is not known whether the Euclidean Steiner tree problem is NP-complete, since membership to the complexity class NP is not known.

==Rectilinear Steiner tree==
{{main article|Rectilinear Steiner tree}}

The rectilinear Steiner tree problem is a variant of the geometric Steiner tree problem in the plane, in which the [[Euclidean distance]] is replaced with the [[rectilinear distance]]. The problem arises in the [[physical design (electronics)|physical design]] of [[electronic design automation]]. In [[VLSI circuit]]s, [[wire routing]] is carried out by wires that are often constrained by design rules to run only in vertical and horizontal directions, so the rectilinear Steiner tree problem can be used to model the routing of nets with more than two terminals.{{sfnp|Sherwani|1993|p=228}}

==Steiner tree in graphs and variants==
Steiner trees have been extensively studied in the context of [[weighted graph]]s. The prototype is, arguably, the '''Steiner tree problem''' '''in graphs'''. Let {{math|1=''G''&nbsp;=&nbsp;(''V'',&nbsp;''E'')}} be an undirected graph with non-negative edge weights c and let {{math|1=''S''&nbsp;⊆&nbsp;''V''}} be a subset of vertices, called '''terminals'''. A '''Steiner tree''' is a tree in ''G'' that spans ''S''. There are two versions of the problem: in the [[optimization problem]] associated with Steiner trees, the task is to find a minimum-weight Steiner tree; in the [[decision problem]] the edge weights are integers and the task is to determine whether a Steiner tree exists whose total weight does not exceed a predefined [[natural number]] ''k''. The decision problem is one of [[Karp's 21 NP-complete problems]]; hence the optimization problem is [[NP-hard]]. Steiner tree problems in graphs are applied to various problems in research and industry,<ref>{{Cite journal|last=Ljubić|first=Ivana|date=2021|title=Solving Steiner trees: Recent advances, challenges, and perspectives|url=https://onlinelibrary.wiley.com/doi/abs/10.1002/net.22005|journal=Networks|language=en|volume=77|issue=2|pages=177–204|doi=10.1002/net.22005|s2cid=229458488 |issn=1097-0037}}</ref> including multicast routing<ref>{{Cite journal|last1=Novak|first1=Roman|last2=Rugelj|first2=Joz̆e|last3=Kandus|first3=Gorazd|date=2001-10-01|title=A note on distributed multicast routing in point-to-point networks|url=https://www.sciencedirect.com/science/article/pii/S0305054800000290|journal=Computers & Operations Research|language=en|volume=28|issue=12|pages=1149–1164|doi=10.1016/S0305-0548(00)00029-0|issn=0305-0548}}</ref> and bioinformatics.<ref>{{Cite journal|last1=Klimm|first1=Florian|last2=Toledo|first2=Enrique M.|last3=Monfeuga|first3=Thomas|last4=Zhang|first4=Fang|last5=Deane|first5=Charlotte M.|last6=Reinert|first6=Gesine|date=2020-11-02|title=Functional module detection through integration of single-cell RNA sequencing data with protein–protein interaction networks|journal=BMC Genomics|volume=21|issue=1|pages=756|doi=10.1186/s12864-020-07144-2|issn=1471-2164|pmc=7607865|pmid=33138772 |doi-access=free }}</ref>

A special case of this problem is when ''G'' is a [[complete graph]], each vertex {{math|1=''v''&nbsp;∈&nbsp;''V''}} corresponds to a point in a [[metric space]], and the edge weights ''w''(''e'') for each ''e''&nbsp;∈&nbsp;''E'' correspond to distances in the space. Put otherwise, the edge weights satisfy the [[triangle inequality]]. This variant is known as the '''metric Steiner tree problem'''. Given an instance of the (non-metric) Steiner tree problem, we can transform it in polynomial time into an equivalent instance of the metric Steiner tree problem; the transformation preserves the approximation factor.{{sfnp|Vazirani|2003|pp=27–28}}

While the Euclidean version admits a PTAS, it is known that the metric Steiner tree problem is [[APX-complete]], i.e., unless [[P = NP]], it is impossible to achieve approximation ratios that are arbitrarily close to 1 in polynomial time. There is a polynomial-time algorithm that [[Approximation algorithm|approximates]] the minimum Steiner tree to within a factor of <math>\ln(4) + \varepsilon\approx1.386</math>;{{sfnp|Byrka|Grandoni|Rothvoß|Sanita|2010}}
however, approximating within a factor <math>96/95\approx 1.0105</math> is NP-hard.{{sfnp|Chlebík|Chlebíková|2008}} For the restricted case of Steiner Tree problem with distances 1 and 2, a 1.25-approximation algorithm is known.{{sfnp|Berman|Karpinski|Zelikovsky|2009}} Karpinski and [[Alexander Zelikovsky]] constructed PTAS for the dense instances of Steiner Tree problems.{{sfnp|Karpinski|Zelikovsky|1998}}

In a special case of the graph problem, the Steiner tree problem for [[quasi-bipartite graph]]s, ''S'' is required to include at least one endpoint of every edge in ''G''.

The Steiner tree problem has also been investigated in higher dimensions and on various surfaces. Algorithms to find the Steiner minimal tree have been found on the sphere, torus, [[projective plane]], wide and narrow cones, and others.{{sfnp|Smith|Winter|1995|p=361}}

Other generalizations of the Steiner tree problem are the '''''k''-edge-connected Steiner network problem''' and the '''''k''-vertex-connected Steiner network problem''', where the goal is to find a [[k-edge-connected graph|''k''-edge-connected graph]] or a [[k-vertex-connected graph|''k''-vertex-connected graph]] rather than any connected graph. A further well-studied<ref>{{Cite journal |last1=Kerivin |first1=Hervé |last2=Mahjoub |first2=A. Ridha |date=2005 |title=Design of Survivable Networks: A survey |url=https://onlinelibrary.wiley.com/doi/10.1002/net.20072 |journal=Networks |language=en |volume=46 |issue=1 |pages=1–21 |doi=10.1002/net.20072 |s2cid=8165318 |issn=0028-3045}}</ref> generalization is the '''survivable network design problem (SNDP)''' where the task is to connect each vertex pair with a given number (possibly 0) of edge- or vertex-disjoint paths.

The Steiner problem has also been stated in the general setting of metric spaces and for possibly infinitely many points.{{sfnp|Paolini|Stepanov|2012}}

==Approximating the Steiner tree==

The general graph Steiner tree problem can be approximated by computing the minimum spanning tree of the subgraph of the metric closure of the graph induced by the terminal vertices, as first published in 1981 by Kou et al.{{sfnp|Kou|Markowsky|Berman|1981}} The metric closure of a graph <math>G</math> is the complete graph in which each edge is weighted by the shortest path distance between the nodes in <math>G</math>. This algorithm produces a tree whose weight is within a <math>2 - 2/t</math> factor of the weight of the optimal Steiner tree where <math>t</math> is the number of leaves in the optimal Steiner tree; this can be proven by considering a traveling salesperson tour on the optimal Steiner tree. This approximate solution is computable in <math>O(|S| |V|^2) </math> [[Time complexity#Polynomial time|polynomial time]] by first solving the [[Shortest path problem#All-pairs shortest paths|all-pairs shortest paths problem]] to compute the metric closure, then by solving the [[minimum spanning tree|minimum spanning tree problem]].

Another popular algorithm to approximate the Steiner tree in graphs was published by Takahashi and Matsuyama in 1980.{{sfnp|Takahashi|Matsuyama|1980}} Their solution incrementally builds up the Steiner tree by starting from an arbitrary vertex, and repeatedly adding the shortest path from the tree to the nearest vertex in <math>S</math> that has not yet been added. This algorithm also has <math> O(|S| |V|^2)</math> running time, and produces a tree whose weight is within <math>2 - 2/|S|</math> of optimal.

In 1986, Wu et al.{{sfnp|Wu|Widmayer|Wong|1986}} improved dramatically on the running time by avoiding precomputation of the all-pairs shortest paths. Instead, they take a similar approach to [[Kruskal's algorithm]] for computing a minimum spanning tree, by starting from a forest of <math>|S|</math> disjoint trees, and "growing" them simultaneously using a breadth-first search resembling [[Dijkstra's algorithm]] but starting from multiple initial vertices. When the search encounters a vertex that does not belong to the current tree, the two trees are merged into one. This process is repeated until only one tree remains. By using a [[Heap (data structure)]] to implement the priority queue and a [[disjoint-set data structure]] to track to which tree each visited vertex belongs, this algorithm achieves <math>O(|E| \log |V|)</math> running time, although it does not improve on the <math>2 - 2/t</math> cost ratio from Kou et al.

A series of papers provided approximation algorithms for the minimum Steiner tree problem with approximation ratios that improved upon the <math>2 - 2/t</math> ratio. This sequence culminated with Robins and Zelikovsky's algorithm in 2000 which improved the ratio to 1.55 by iteratively improving upon the minimum cost terminal spanning tree. More recently, however, Byrka et al. proved an <math>\ln(4) + \varepsilon \le 1.39</math> approximation using a linear programming relaxation and a technique called iterative, randomized rounding.{{sfnp|Byrka|Grandoni|Rothvoß|Sanita|2010}}

==Parameterized complexity of Steiner tree==

The general graph Steiner tree problem is known to be [[Parameterized complexity#FPT|fixed-parameter tractable]], with the number of terminals as a parameter, by the Dreyfus-Wagner algorithm.{{sfnp|Dreyfus|Wagner|1971}}{{sfnp|Levin|1971}} The running time of the Dreyfus-Wagner algorithm is <math>3^{|S|} \text{poly}(n)</math>, where {{mvar|n}} is the number of vertices of the graph and {{mvar|S}} is the set of terminals. Faster algorithms exist, running in <math>c^{|S|} \text{poly}(n)</math> time for any <math>c > 2</math> or, in the case of small weights, <math>2^{|S|} \text{poly}(n) W</math> time, where {{mvar|W}} is the maximum weight of any edge.{{sfnp|Fuchs|Kern|Mölle|Richter|2007}}{{sfnp|Björklund|Husfeldt|Kaski|Koivisto|2007}} A disadvantage of the aforementioned algorithms is that they use [[Space complexity|exponential space]]; there exist polynomial-space algorithms running in <math>2^{|S|} \text{poly}(n) W</math> time and <math>(7.97)^{|S|} \text{poly}(n) \log W</math> time.{{sfnp|Lokshtanov|Nederlof|2010}}{{sfnp|Fomin|Kaski|Lokshtanov|Panolan|2015}}

It is known that the general graph Steiner tree problem does not have a parameterized algorithm running in <math>2^{\epsilon t} \text{poly}(n)</math> time for any <math>\epsilon < 1</math>, where {{mvar|t}} is the number of edges of the optimal Steiner tree, unless the [[Set cover problem]] has an algorithm running in <math>2^{\epsilon n} \text{poly}(m)</math> time for some <math>\epsilon < 1</math>, where {{mvar|n}} and {{mvar|m}} are the number of elements and the number of sets, respectively, of the instance of the set cover problem.{{sfnp|Cygan|Dell|Lokshtanov|Marx|2016}} Furthermore, it is known that the problem does not admit a [[Kernelization|polynomial kernel]] unless <math>\textsf{coNP} \subseteq \textsf{NP/poly}</math>, even parameterized by the number of edges of the optimal Steiner tree and if all edge weights are 1.{{sfnp|Dom|Lokshtanov|Saurabh|2014}}

== Parameterized approximation of Steiner tree ==
While the graph Steiner tree problem does not admit a [[Kernelization|polynomial kernel]] unless <math>\textsf{coNP} \subseteq \textsf{NP/poly}</math> parameterized by the number of terminals, it does admit a [[Parameterized approximation algorithm#Approximate kernelization|polynomial-sized approximate kernelization scheme]] (PSAKS): for any <math>\varepsilon>0</math> it is possible to compute a polynomial-sized kernel, which looses only a <math>1+\varepsilon</math> factor in the solution quality.<ref>{{Cite book |last1=Lokshtanov |first1=Daniel |last2=Panolan |first2=Fahad |last3=Ramanujan |first3=M. S. |last4=Saurabh |first4=Saket |title=Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing |chapter=Lossy kernelization |date=2017-06-19 |chapter-url=https://doi.org/10.1145/3055399.3055456 |series=STOC 2017 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=224–237 |doi=10.1145/3055399.3055456 |isbn=978-1-4503-4528-6|s2cid=14599219 |url=http://wrap.warwick.ac.uk/113741/1/WRAP-Lossy-Kernelization-Ramanujan-2019.pdf }}</ref>

When parameterizing the graph Steiner tree problem by the number {{mvar|p}} of non-terminals (Steiner vertices) in the optimum solution, the problem is [[Parameterized complexity#W hierarchy|W[1]-hard]] (in contrast to the parameterization by the number of terminals, as mentioned above). At the same time the problem is [[APX-complete]] and thus does not admit a [[Polynomial-time approximation scheme|PTAS]], unless [[P = NP]]. However, a [[Parameterized approximation algorithm|parameterized approximation scheme]] exists, which for any <math>\varepsilon>0</math> computes a <math>(1+\varepsilon)</math>-approximation in <math>2^{O(p^2/\varepsilon^4)}n^{O(1)}</math> time.<ref name=":0">{{Cite journal |last1=Dvořák |first1=Pavel |last2=Feldmann |first2=Andreas E. |last3=Knop |first3=Dušan |last4=Masařík |first4=Tomáš |last5=Toufar |first5=Tomáš |last6=Veselý |first6=Pavel |date=2021-01-01 |title=Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices |url=https://epubs.siam.org/doi/10.1137/18M1209489 |journal=SIAM Journal on Discrete Mathematics |volume=35 |issue=1 |pages=546–574 |doi=10.1137/18M1209489 |s2cid=3581913 |issn=0895-4801|arxiv=1710.00668 }}</ref> Also a PSAKS exists for this parameterization.<ref name=":0" />

==Steiner ratio==

The '''Steiner ratio''' is the [[supremum]] of the ratio of the total length of the minimum spanning tree to the minimum Steiner tree for a set of points in the Euclidean plane.{{sfnp|Ganley|2004}}

In the Euclidean Steiner tree problem, the [[Gilbert–Pollak conjecture]] is that the Steiner ratio is <math>\tfrac{2}{\sqrt{3}}\approx 1.1547</math>, the ratio that is achieved by three points in an [[equilateral triangle]] with a spanning tree that uses two sides of the triangle and a Steiner tree that connects the points through the centroid of the triangle. Despite earlier claims of a proof,<ref>''The New York Times'', 30 Oct 1990, reported that a proof had been found, and that [[Ronald Graham]], who had offered $500 for a proof, was about to mail a check to the authors.</ref> the conjecture is still open.{{sfnp|Ivanov|Tuzhilin|2012}} The best widely accepted [[upper bound]] for the problem is 1.2134, by {{harvtxt|Chung|Graham|1985}}.

For the rectilinear Steiner tree problem, the Steiner ratio is exactly <math>\tfrac{3}{2}</math>, the ratio that is achieved by four points in a square with a spanning tree that uses three sides of the square and a Steiner tree that connects the points through the center of the square.{{sfnp|Hwang|1976}} More precisely, for <math>L_1</math> distance the square should be tilted at <math>45^{\circ}</math> with respect to the coordinate axes, while for <math>L_{\infty}</math> distance the square should be axis-aligned.

==See also==
*[[Opaque forest problem]]
*[[Travelling salesman problem]]

==Notes==
{{reflist}}

==References==
{{refbegin|30em}}
*{{cite conference
|last1= Berman |first1= Piotr
|last2= Karpinski |first2= Marek | authorlink2 = Marek Karpinski
|last3= Zelikovsky |first3= Alexander
|year= 2009
|contribution= 1.25-approximation algorithm for Steiner tree problem with distances 1 and 2
|series= Lecture Notes in Computer Science
|title=Algorithms and Data Structures: 11th International Symposium, WADS 2009, Banff, Canada, August 21–23, 2009, Proceedings
|volume= 5664
|pages= 86–97
|doi=10.1007/978-3-642-03367-4_8
|arxiv= 0810.1851
|isbn= 978-3-642-03366-7
}}
*{{cite journal
|last1= Bern
|first1= Marshall W.
|last2= Graham
|first2= Ronald L. | author2-link = Ronald Graham
|year= 1989
|title= The shortest-network problem
|journal= Scientific American
|volume= 260
|pages= 84–89
|doi=10.1038/scientificamerican0189-84
|issue=1
|bibcode= 1989SciAm.260a..84B
}}
*{{cite conference
|last1=Björklund | first1=Andreas
|last2=Husfeldt | first2=Thore
|last3=Kaski | first3=Petteri
|last4=Koivisto | first4=Mikko
|year=2007
|contribution=Fourier Meets Möbius: Fast Subset Convolution
|title=[[Symposium on Theory of Computing|Proceedings of the 39th ACM Symposium on Theory of Computing]]
|pages=67–74
|doi=10.1145/1250790.1250801
|arxiv=cs/0611101| isbn=978-1-59593-631-8
}}
*{{cite conference|last1=Byrka|first1=J.|last2=Grandoni|first2=F.|last3=Rothvoß|first3=T.|last4=Sanita|first4=L.|year=2010|contribution=An improved LP-based approximation for Steiner tree|doi=10.1145/1806689.1806769|title = [[Symposium on Theory of Computing|Proceedings of the 42nd ACM Symposium on Theory of Computing]]|pages= 583–592 |isbn=978-1-4503-0050-6 |citeseerx=10.1.1.177.3565}}
*{{cite journal|last1=Chlebík|first1=Miroslav|last2=Chlebíková|first2=Janka|author2-link=Janka Chlebíková|year=2008|title=The Steiner tree problem on graphs: Inapproximability results|doi=10.1016/j.tcs.2008.06.046|journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]]|volume=406|issue=3|pages=207–214|doi-access=free}}
*{{cite conference
 | last1 = Chung | first1 = F. R. K. | author1-link = Fan Chung
 | last2 = Graham | first2 = R. L. | author2-link = Ronald Graham
 | contribution = A new bound for Euclidean Steiner minimal trees
 | doi = 10.1111/j.1749-6632.1985.tb14564.x
 | mr = 809217
 | pages = 328–346
 | publisher = New York Academy of Science | location = New York
 | series = Annals of the New York Academy of Science
 | title = Discrete geometry and convexity (New York, 1982)
 | volume = 440
 | year = 1985
 | bibcode = 1985NYASA.440..328C}}
*{{cite book |first=Dietmar|last=Cieslik |title=Steiner Minimal Trees |year=1998 |isbn=0-7923-4983-0 |pages=319|publisher=Springer }}
*{{Cite web
 | last1=Crescenzi | first1=Pierluigi
 | last2=Kann | first2=Viggo
 | last3=Halldórsson | first3=Magnús
 | last4=Karpinski | first4=Marek | authorlink4=Marek Karpinski
 | last5=Woeginger | first5=Gerhard | author5-link = Gerhard J. Woeginger
 | work=A Compendium of NP Optimization Problems
 | title=Minimum geometric Steiner tree
 | url=https://www.csc.kth.se/~viggo/wwwcompendium/node79.html
 | year=2000
 }}
*{{cite journal
|last1=Cygan | first1=Marek
|last2=Dell | first2=Holger
|last3=Lokshtanov | first3=Daniel
|last4=Marx | first4=Dániel
|last5=Nederlof | first5=Jesper
|last6=Okamoto | first6=Yoshio
|last7=Paturi | first7=Ramamohan
|last8=Saurabh | first8=Saket
|last9=Wahlström | first9=Magnus
|title=On Problems as Hard as CNF-SAT
|journal=ACM Transactions on Algorithms
| year=2016
|volume=12
|number=3
|pages=41:1–41:24
|doi=10.1145/2925416| s2cid=7320634
| url=http://eprints.sztaki.hu/9047/
|arxiv=1112.2275
}}
*{{cite journal
|last1=Dom | first1=Michael
|last2=Lokshtanov | first2=Daniel
|last3=Saurabh | first3=Saket
|title=Kernelization Lower Bounds Through Colors and IDs
|journal=ACM Transactions on Algorithms
|year=2014
|volume=11
|number=2
|pages=13:1–13:20
|doi=10.1145/2650261| s2cid=13570734
}}
*{{cite journal
|last1=Dreyfus | first1= S.E.
|last2=Wagner | first2 = R.A.
|year=1971
|title=The Steiner problem in graphs
|journal=Networks
|volume=1
|issue=3
|pages=195–207
|doi=10.1002/net.3230010302}}
*{{cite conference
|last1=Fomin | first1=Fedor V.
|last2=Kaski | first2=Petteri
|last3=Lokshtanov | first3=Daniel
|last4=Panolan | first4=Fahad
|last5=Saurabh | first5=Saket
|year=2015
|title=[[International Colloquium on Automata, Languages and Programming|Automata, Languages, and Programming – 42nd International Colloquium, ICALP 2015, Proceedings, Part I]]
| series=Lecture Notes in Computer Science
| volume=9134
|contribution=Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree
|pages=494–505
|doi=10.1007/978-3-662-47672-7_40|hdl=1956/23311
| isbn=978-3-662-47671-0
|hdl-access=free
}}
*{{cite journal
|last1=Fuchs | first1=Benjamin
|last2=Kern | first2=Walter
|last3=Mölle | first3=Daniel
|last4=Richter | first4=Stefan
|last5=Rossmanith | first5=Peter
|last6=Wang | first6=Xinhui
|title=Dynamic Programming for Minimum Steiner Trees
|journal=Theory of Computing Systems
|year=2007
|volume=41
|issue=3
|pages=493–500
|doi=10.1007/s00224-007-1324-4| s2cid=7478978
| url=http://e-archive.informatik.uni-koeln.de/492/2/zaik2005-492.pdf
}}
*{{Cite book | first=Joseph L. | last=Ganley | url=https://xlinux.nist.gov/dads/HTML/steinerratio.html | contribution=Steiner ratio | title=Dictionary of Algorithms and Data Structures | editor-first=Paul E. | editor-last=Black | publisher=U.S. National Institute of Standards and Technology | year=2004 | access-date=2012-05-24 }}
* {{Garey-Johnson}}, {{Page numbers|208–209}}, problems ND12 and ND13.
*{{cite journal
 | last = Hwang | first = F. K.
 | doi = 10.1137/0130013
 | issue = 1
 | journal = SIAM Journal on Applied Mathematics
 | pages = 104–114
 | title = On Steiner minimal trees with rectilinear distance
 | volume = 30
 | year = 1976
 }}
* {{cite book |first1=F. K.|last1=Hwang|first2=D. S.|last2=Richards|first3=P.|last3=Winter |title=The Steiner Tree Problem |publisher=[[Elsevier]] |place=[[North-Holland Publishing Company|North-Holland]] |year=1992 |isbn=0-444-89098-X |series=Annals of Discrete Mathematics |volume=53}}
* {{cite book
|last1= Ivanov |first1= Alexander
|last2= Tuzhilin |first2= Alexey 
 |title=Minimal Networks: The Steiner Problem and Its Generalizations |url= https://archive.org/details/minimalnetworkss0000ivan |url-access= registration |publisher=[[CRC Press]] |place=N.W., Boca Raton, Florida |year=1994 |isbn=978-0-8493-8642-8}}
* {{cite book
|last1= Ivanov |first1= Alexander
|last2= Tuzhilin |first2= Alexey 
 |title=Branching solutions to one-dimensional variational problems |publisher=[[World Scientific]] |place=Singapore-New Jersey-London-Hong Kong |year=2000 |isbn=978-981-02-4060-8}}
* {{cite book
|last1= Ivanov |first1= Alexander
|last2= Tuzhilin |first2= Alexey 
 |title=Extreme Networks Theory |place=Moscow-Izhevsk |publisher=Institute of Computer Investigations |year=2003 |language=Russian |isbn=5-93972-292-X}}
*{{cite journal
|last1= Ivanov |first1= Alexander
|last2= Tuzhilin |first2= Alexey 
 |title=The Steiner ratio Gilbert–Pollak conjecture is still open: Clarification statement|journal=Algorithmica|year=2012|volume=62|issue=1–2|pages=630–632|doi=10.1007/s00453-011-9508-3|s2cid= 7486839
}}
*{{cite journal
|last1= Ivanov |first1= Alexander
|last2= Tuzhilin |first2= Alexey 
|year= 2015
|title= Branched coverings and Steiner ratio
|journal= International Transactions in Operational Research
|volume= 23
|issue= 5
|pages= 875–882
|doi=10.1111/itor.12182
|arxiv=1412.5433|s2cid= 3386263
}}
*{{cite journal|last1=Juhl|first1=D.|last2=Warme|first2=D.M.|last3=Winter |first3=P.|last4=Zachariasen|first4=M.|title=The GeoSteiner Software Package for computing Steiner trees in the plane: an updated computational study|journal=  Mathematical Programming Computation|date=January 2018 |volume=10 |issue=4 |pages=487–532|doi=10.1007/s12532-018-0135-8|s2cid=255616114 |url=https://curis.ku.dk/portal/da/publications/the-geosteiner-software-package-for-computing-steiner-trees-in-the-plane(33ef119c-99c9-4511-9455-296ff28ee2eb).html }}
*{{cite journal|last1=Rehfeldt|first1=D.|last2=Koch|first2=T.|title=Implications, conflicts, and reductions for Steiner trees|journal= Mathematical Programming|date=February 2023 |volume=197|issue=2|pages=903–966|doi=10.1007/s10107-021-01757-5|s2cid=231842568 |doi-access=free}}
* {{cite conference
 | first1=Marek | last1=Karpinski
 | first2=Alexander | last2=Zelikovsky
 | contribution=Approximating dense cases of covering problems
 | pages=169–178
 | year=1998
 | contribution-url=https://books.google.com/books?id=IMmuF0RZk1MC&pg=PA169
 | title=Proceedings of the DIMACS Workshop on Network Design: Connectivity and Facilities Location
 | publisher=American Mathematical Society
 | series=DIMACS Series in Discrete Mathematics and Theoretical Computer Science
 | volume=40}}
*{{cite book
 | last1=Korte | first1=Bernhard | author1-link = Bernhard Korte
 | last2=Vygen | first2=Jens
 | title=Combinatorial Optimization: Theory and Algorithms
 | publisher=[[Springer Science+Business Media|Springer]]
 | year=2006
 | edition=3rd
 | isbn=3-540-25684-9
 | chapter=Section 20.1
}}
*{{cite journal |last1=Kou |first1=L. |last2=Markowsky |first2=G. |last3=Berman |first3=L. |title=A fast algorithm for Steiner trees |journal=Acta Informatica |date=1 June 1981 |volume=15 |issue=2 |pages=141–145 |doi=10.1007/BF00288961|s2cid=21057232 }}
*{{cite journal
|last1=Levin | first1=A. Yu.
|year=1971
|title=Algorithm for the shortest connection of a group of graph vertices
|journal=Soviet Mathematics Doklady
|volume=12
|pages=1477–1481}}
*{{cite conference
|last1 = Lokshtanov | first1=Daniel
|last2 = Nederlof | first2=Jesper
|contribution = Saving space by algebraization
|title=[[Symposium on Theory of Computing|Proceedings of the 42nd ACM Symposium on Theory of Computing]]
|year=2010
|pages=321–330
|doi=10.1145/1806689.1806735| isbn=978-1-4503-0050-6
}}
*{{cite journal|last1=Paolini|first1=E. |last2=Stepanov|first2=E.|title=Existence and regularity results for the Steiner problem|journal=Calc. Var. Partial Diff. Equations|year=2012|volume=46 |issue=3–4 |pages=837–860 |doi=10.1007/s00526-012-0505-4|hdl=2158/600141 |s2cid=55793499 |url=https://flore.unifi.it/bitstream/2158/600141/1/final-for-CalcVar.pdf|hdl-access=free}}
*{{cite conference
 | last1 = Robins
 | first1 = Gabriel
 | last2 = Zelikovsky
 | first2 = Alexander
 | contribution = Improved Steiner Tree Approximation in Graphs
 | contribution-url = http://dl.acm.org/citation.cfm?id=338219.338638
 | isbn = 0-89871-453-2
 | location = Philadelphia, PA, USA
 | pages = [https://archive.org/details/proceedingsofele0000acms/page/770 770–779]
 | publisher = Society for Industrial and Applied Mathematics
 | title = Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '00)
 | year = 2000
 | url = https://archive.org/details/proceedingsofele0000acms/page/770
 }}
*{{cite book|title=Algorithms for VLSI Physical Design Automation|first=Naveed A.|last=Sherwani
| publisher = Kluwer Academic Publishers | year = 1993 | isbn = 9781475722192 }}
*{{cite book |editor1-first=Ding-Zhu|editor1-last=Du|editor2-first=Frank|editor2-last=Hwang |title=Computing in Euclidean geometry |publisher=World Scientific Publishing Co |location=River Edge, NJ |year=1995 |isbn=981-02-1876-1 |series=Lecture Notes Series on Computing |volume=4 | edition=2nd|contribution=Computational geometry and topological network design|first1=J. M.|last1=Smith|first2=P.|last2=Winter|pages=351–451}}
*{{cite journal |last1=Takahashi |first1=Hiromitsu |last2=Matsuyama |first2=Akira |title=An approximate solution for the Steiner problem in graphs |journal=Math. Japonica |date=1980 |volume=24 |issue=6 |pages=573–577}}
*{{cite book
 | last = Vazirani | first = Vijay V. | authorlink = Vijay Vazirani
 | title = Approximation Algorithms
 | publisher = Springer
 | year = 2003
 | place = Berlin
 | isbn = 3-540-65367-8
 }}
*{{cite book
 | last1=Wu | first1=Bang Ye
 | last2=Chao | first2=Kun-Mao
 | title=Spanning Trees and Optimization Problems
 | publisher=Chapman & Hall/CRC
 | year=2004
 | isbn=1-58488-436-3
 | chapter=Chapter 7
}}
*{{cite journal |last1=Wu |first1=Y. F. |last2=Widmayer |first2=P. |last3=Wong |first3=C. K. |title=A faster approximation algorithm for the Steiner problem in graphs |journal=Acta Informatica |date=May 1986 |volume=23 |issue=2 |pages=223–229 |doi=10.1007/bf00289500 |s2cid=7772232 }}
{{refend}}

==External links==
{{Commons category|Steiner tree problem}}
*[http://www.geosteiner.com/ GeoSteiner] (Software for solving Euclidean and rectilinear Steiner tree problems; source available, free for non-commercial use)
*[https://scipjack.zib.de/ SCIP-Jack] (Software for solving the Steiner tree problem in graphs and 14 variants, e.g., prize-collecting Steiner tree problem; free for non-commercial use)
*[http://nuclear.llnl.gov/CNP/apt/apt/aptsver.html Fortran subroutine] for finding the Steiner vertex of a triangle (i.e., [[Fermat point]]), its distances from the triangle vertices, and the relative vertex weights.
*[http://phylomurka.sf.net Phylomurka] (Solver for small-scale Steiner tree problems in graphs)
*[https://www.youtube.com/watch?v=PI6rAOWu-Og https://www.youtube.com/watch?v=PI6rAOWu-Og] (Movie: solving the Steiner tree problem with water and soap)
* {{Citation | url = https://www.researchgate.net/publication/316921061 | title = DCCast: Efficient Point to Multipoint Transfers Across Datacenters | contribution = Using Steiner Trees to Minimize Average Completion Times of Bulk Data Transfers | publisher = USENIX Association| last1 = Noormohammadpour | first1 = Mohammad | last2 = Raghavendra | first2 = Cauligi S. | last3 = Rao | first3 = Sriram | last4 = Kandula | first4 = Srikanth | year = 2017 | arxiv = 1707.02096 }}
*{{springer|title=Steiner tree problem|id=s/s110270|last=Hazewinkel|first=M.}}
*[http://theory.cs.uni-bonn.de/info5/steinerkompendium/ M. Hauptmann, M. Karpinski (2013): A Compendium on Steiner Tree Problems] 

[[Category:NP-complete problems]]
[[Category:Trees (graph theory)]]
[[Category:Computational problems in graph theory]]
[[Category:Geometric algorithms]]
[[Category:Geometric graphs]]