Steiner tree problem
E530318
NP-hard problem
combinatorial optimization problem
geometric optimization problem
graph theory problem
The Steiner tree problem is a classic optimization problem in combinatorial mathematics and computer science that seeks the shortest network of line segments connecting a given set of points, potentially adding extra intermediate points to minimize total length.
Statements (49)
| Predicate | Object |
|---|---|
| instanceOf |
NP-hard problem
ⓘ
combinatorial optimization problem ⓘ geometric optimization problem ⓘ graph theory problem ⓘ |
| allows | introduction of additional intermediate points ⓘ |
| alsoCalled | Steiner minimal tree problem NERFINISHED ⓘ |
| complexityClass |
NP-complete in graphs
ⓘ
NP-hard in Euclidean plane ⓘ |
| constraint |
all terminal points must be connected
ⓘ
resulting network must be a tree ⓘ |
| edgeWeights |
can represent Euclidean distances
ⓘ
can represent arbitrary nonnegative costs ⓘ |
| field |
combinatorics
ⓘ
operations research ⓘ theoretical computer science ⓘ |
| goal | find a minimum-length network connecting a given set of points ⓘ |
| hasApproximation | polynomial-time approximation schemes in some metric spaces ⓘ |
| hasProperty |
admits approximation algorithms
ⓘ
admits heuristic algorithms ⓘ exact solution is computationally expensive for large instances ⓘ generalizes the minimum spanning tree problem ⓘ |
| hasSpecialCase |
Steiner tree in series-parallel graphs
NERFINISHED
ⓘ
Steiner tree in trees (polynomial-time solvable) ⓘ |
| hasVariant |
Euclidean Steiner tree problem
ⓘ
Steiner forest problem NERFINISHED ⓘ Steiner tree problem in graphs NERFINISHED ⓘ directed Steiner tree problem ⓘ group Steiner tree problem ⓘ rectilinear Steiner tree problem ⓘ |
| historicalOrigin | 19th century geometry ⓘ |
| input |
finite set of terminal vertices
ⓘ
underlying metric space or graph ⓘ |
| namedAfter | Jakob Steiner NERFINISHED ⓘ |
| objectiveFunction | total length of edges in the connecting network ⓘ |
| optimizationType | minimization problem ⓘ |
| output |
set of Steiner points that minimize total length
ⓘ
tree of minimum total edge length connecting all terminals ⓘ |
| relatedTo |
Steiner system
NERFINISHED
ⓘ
minimum spanning tree problem ⓘ shortest path problem ⓘ |
| solutionStructure |
Steiner points in Euclidean plane have degree 3
ⓘ
angles at Steiner points in Euclidean plane are 120 degrees apart ⓘ |
| studiedIn |
algorithm design
ⓘ
computational geometry ⓘ |
| usedIn |
VLSI design
ⓘ
network design ⓘ phylogenetic tree reconstruction ⓘ transportation network planning ⓘ wireless communication networks ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.