Steiner Tree

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).

---

REFERENCES

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.

اخر الاخبار

اخبار العتبة العباسية المقدسة

قسم حفظ النظام ينهي استعداداته الخاصة بحفل تخرج طالبات الجامعات العاشر

العتبة العباسية المقدسة تنشر أكاليل الزهور ومظاهر الفرح بمناسبة ذكرى ولادة أمير المؤمنين (عليه السلام)

مجمع الشيخ الكليني يواصل تحضيراته لاستقبال المشاركات في حفل تخرج طالبات الجامعات العاشر

وصول المشاركات في فعاليات مهرجان روح النبوة الثقافي النسوي العالمي الثامن إلى كربلاء

المزيد

الآخبار الصحية

ماذا يحدث لجسمك عند تناول الوجبات السريعة يوميا؟

لصحة عظام المرأة.. الشاي أفضل أم القهوة؟

لبناء العضلات وإنقاص الوزن.. ما أفضل توقيت لتناول البيض؟

أطعمة صحية تساعد على التعافي من "الإنفلونزا الخارقة"

المزيد

الآخبار التكنلوجية

دراسة تكشف قدرة الحيتان على سماع الأصوات منخفضة وعالية التردد من مسافة بعيدة

تجربة جديدة: الأسفلت المدعوم بالطحالب يقاوم الحفر ويقلل الانبعاثات الكربونية

تسريبات تكشف ملامح أول هاتف قابل للطي من "أبل"

رصد نوع نادر من القطط في تايلاند للمرة الأولى منذ عقود

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength