Read More
Date: 28-3-2022
1250
Date: 8-3-2022
1413
Date: 28-7-2016
1224
|
The Steiner tree of some subset of the vertices of a graph is a minimum-weight connected subgraph of that includes all the vertices. It is always a tree. Steiner trees have practical applications, for example, in the determination of the shortest total length of wires needed to join some number of points (Hoffman 1998, pp. 164-165).
The determination of a Steiner tree is NP-complete and hard even to approximate. There is 1.55-approximate algorithm due to Robins and Zelikovski (2000), but approximation within 95/94 is known to be NP-hard (Chlebik and Chlebikova 2002).
Chlebik, M. and J.Chlebikova, J. "Approximation Hardness of the Steiner Tree Problem on Graphs." Proc. 8th Scandinavian Workshop on Algorithm Theory (SWAT). Springer-Verlag, pp. 170-179, 2002.
Chopra, S. and Rao, M. R. "The Steiner Tree Problem 1: Formulations, Compositions, and Extension of Facets." Mathematical Programming 64, 209-229, 1994.
Chopra, S. and Rao, M. R. "The Steiner Tree Problem 2: Properties and Classes of Facets." Mathematical Programming 64, 231-246, 1994.
Chung, F. R. K.; Gardner, M.; and Graham, R. L. "Steiner Trees on a Checkerboard." Math. Mag. 62, 83-96, 1989.
Cieslik, D. Steiner Minimal Trees. Amsterdam: Kluwer, 1998.
Du, D.-Z.; Smith, J. M.; and Rubinstein, J. H. Advances in Steiner Trees. Dordrecht, Netherlands: Kluwer, 2000.Ganley, J. "The Steiner Tree Page." http://ganley.org/steiner/.Hoffman, P. The Man Who Loved Only Numbers: The Story of Paul Erdős and the Search for Mathematical Truth. New York: Hyperion, 1998.
Hwang, F.; Richards, D.; and Winter, P. The Steiner Tree Problem. Amsterdam, Netherlands: North-Holland, 1992.
Ivanov, A. O. and Tuzhilin, A. A. Minimal Networks: The Steiner Problem and Its Generalizations. Boca Raton, FL: CRC Press, 1994.
Robins, G. and Zelikovski, A. "Improved Steiner Tree Approximation in Graphs." In Proc. 11th ACM-SIAM Symposium on Discrete Algorithms. pp. 770-779, 2000.
Skiena, S. S. "Steiner Tree." §8.5.10 in The Algorithm Design Manual. New York: Springer-Verlag, pp. 339-342, 1997.
|
|
دراسة يابانية لتقليل مخاطر أمراض المواليد منخفضي الوزن
|
|
|
|
|
اكتشاف أكبر مرجان في العالم قبالة سواحل جزر سليمان
|
|
|
|
|
المجمع العلمي ينظّم ندوة حوارية حول مفهوم العولمة الرقمية في بابل
|
|
|