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.
All labels observed (1)
| Label | Occurrences |
|---|---|
| Steiner tree problem canonical | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T5570708 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: Steiner tree problem Context triple: [Fermat point, relatedConcept, Steiner tree problem]
-
A.
Kruskal
Kruskal is a surname most prominently associated with American mathematician Martin David Kruskal, known for his work in soliton theory and nonlinear science.
-
B.
Dijkstra
Dijkstra is a renowned Dutch computer scientist best known for his pioneering work in algorithms, including Dijkstra's shortest path algorithm, and for his influential contributions to programming methodology and software engineering.
-
C.
Fermat point
The Fermat point is a special point inside a triangle that minimizes the total distance to the triangle’s three vertices.
-
D.
Eppstein
Eppstein is a small historic town in the German state of Hesse, known for its medieval castle and scenic location in the Taunus mountains.
-
E.
Conway's 99-graph problem
Conway's 99-graph problem is an unsolved combinatorial question in graph theory, posed by John H. Conway, concerning the existence and properties of a hypothetical 99-vertex graph with highly constrained adjacency conditions.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: Steiner tree problem Target entity description: 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.
-
A.
Kruskal
Kruskal is a surname most prominently associated with American mathematician Martin David Kruskal, known for his work in soliton theory and nonlinear science.
-
B.
Dijkstra
Dijkstra is a renowned Dutch computer scientist best known for his pioneering work in algorithms, including Dijkstra's shortest path algorithm, and for his influential contributions to programming methodology and software engineering.
-
C.
Fermat point
The Fermat point is a special point inside a triangle that minimizes the total distance to the triangle’s three vertices.
-
D.
Eppstein
Eppstein is a small historic town in the German state of Hesse, known for its medieval castle and scenic location in the Taunus mountains.
-
E.
Conway's 99-graph problem
Conway's 99-graph problem is an unsolved combinatorial question in graph theory, posed by John H. Conway, concerning the existence and properties of a hypothetical 99-vertex graph with highly constrained adjacency conditions.
- F. None of above. chosen
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 ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Steiner tree problem Description of subject: 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.
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.