Statements (24)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
gptkb:mathematical_concept
|
| gptkbp:application |
VLSI design
Network design Phylogenetic tree construction |
| gptkbp:complexity |
NP-complete
|
| gptkbp:defines |
A tree connecting a given set of points (terminals) with minimum total edge length, possibly including additional points (Steiner points).
|
| gptkbp:field |
gptkb:Graph_theory
|
| gptkbp:firstDescribed |
1850s
|
| gptkbp:generalizes |
Minimum spanning tree
|
| gptkbp:hasVariant |
gptkb:Euclidean_Steiner_Tree
gptkb:Rectilinear_Steiner_Tree |
| https://www.w3.org/2000/01/rdf-schema#label |
Steiner Tree
|
| gptkbp:namedAfter |
gptkb:Jakob_Steiner
|
| gptkbp:relatedTo |
mathematical optimization
Minimum spanning tree |
| gptkbp:supportsAlgorithm |
Approximation algorithm
Exact algorithm |
| gptkbp:type |
NP-hard problem
|
| gptkbp:usedIn |
gptkb:Computational_biology
Telecommunications Circuit layout |
| gptkbp:bfsParent |
gptkb:Karp's_21_NP-complete_problems
gptkb:Reducibility_Among_Combinatorial_Problems_(Karp,_1972) |
| gptkbp:bfsLayer |
6
|