Worst-case performance of Rayward-Smith's Steiner tree heuristic (Q1114397): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
| (One intermediate revision by one other user not shown) | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2087598714 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Routing to Multiple Destinations in Computer Networks / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q4142699 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: A fast algorithm for Steiner trees / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: The computation of nearly minimal Steiner trees in graphs / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: On finding steiner vertices / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q3874241 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Steiner problem in networks: A survey / rank | |||
Normal rank | |||
Latest revision as of 10:36, 19 June 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Worst-case performance of Rayward-Smith's Steiner tree heuristic |
scientific article |
Statements
Worst-case performance of Rayward-Smith's Steiner tree heuristic (English)
0 references
1988
0 references
We prove that the worst-case performance of the Steiner tree approximation algorithm by \textit{V. J. Rayward-Smith} (RS) [Int. J. Math. Educ. Sci. Technol. 14, 15-23 (1983; Zbl 0512.05024)] is within two times optimal and that two is the best bound in the sense that there are instances for which RS will do worse than any value less than two.
0 references
NP-complete
0 references
worst-case
0 references
Steiner tree
0 references
approximation algorithm
0 references
optimal
0 references
