Content deleted Content added
fix typos |
m v2.05b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation) |
||
Line 8:
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]], the [[Decision problem|decision variant]] of the Steiner tree problem in graphs is [[NP-complete]] (which implies that the optimization variant 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==
| |||