|
This article is cited in 12 scientific papers (total in 12 papers)
The Steiner problem: A survey
E. N. Gordeev, O. G. Tarastsov
Abstract:
In the last decade the Steiner problem has attracted considerable attention from investigators in the field of discrete optimization. Here we give a brief survey of the fundamental results concerning the properties and algorithms for solving the Steiner problem on a Euclidean plane, the Steiner problem on a plane with a rectangular metric, and the Steiner problem on graphs, and in the latter problem we focus on results obtained after 1985. We consider both exact and heuristic algorithms, their efficiency and the results of numerical experiments. We give examples of probabilistic approaches to the solution of the problem. The final section of the paper is devoted to the Gilbert – Pollak conjecture.
Received: 19.03.1992
Citation:
E. N. Gordeev, O. G. Tarastsov, “The Steiner problem: A survey”, Diskr. Mat., 5:2 (1993), 3–28; Discrete Math. Appl., 3:4 (1993), 339–364
Linking options:
https://www.mathnet.ru/eng/dm674 https://www.mathnet.ru/eng/dm/v5/i2/p3
|
Statistics & downloads: |
Abstract page: | 3809 | Full-text PDF : | 2872 | First page: | 2 |
|