No label defined (Q4934235)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1389815
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1389815 |
Statements
17 January 2000
0 references
insertion heuristic
0 references
Steiner problem
0 references
0.8894436359405518
0 references
0.8851255774497986
0 references
The Steiner problem in graphs is the ``problem of shortest connectivity''. More exactly, consider a (connected) graph \(G= (V,E)\) with a positive cost function \(c\) on the edges. Given a subset \(R\) of \(V\) of required vertices; search a connected subgraph \(H\) of \(G\) which includes all the vertices of \(R\) and is of minimum total cost \(c(H)\). Such subgraph must be a tree and it may contain vertices different from vertices in \(R\). The Steiner problem is NP-hard and many polynomial-time heuristics have been developed to provide at least an approximative solution. The paper introduce the ``insertion heuristic'' which is starting with a minimum spanning tree in the distance graph of \(G\), and improving it by inserting new vertices in the tree. The worst-case scenario of such a heuristic is discussed.
0 references
