स्टाइनर ट्री की समस्या

तीन बिंदुओं के लिए स्टाइनर ट्री A, B, और C (ध्यान दें कि इनके बीच कोई सीधा संबंध नहीं है A, B, C). द स्टाइनर पॉइंट S त्रिभुज के Fermat बिंदु पर स्थित है ABC.

चार बिंदुओं के लिए समाधान—दो स्टाइनर बिंदु हैं, S₁ और S₂

संयोजी गणित में, स्टाइनर ट्री समस्या, या न्यूनतम स्टाइनर ट्री समस्या, जिसका नाम जैकब स्टाइनर के नाम पर रखा गया है, संयोजन अनुकूलन में समस्याओं के एक वर्ग के लिए एक छत्र शब्द है। जबकि स्टाइनर ट्री की समस्याओं को कई सेटिंग्स में तैयार किया जा सकता है, उन सभी को वस्तुओं के दिए गए समूह और पूर्वनिर्धारित उद्देश्य फ़ंक्शन के लिए एक इष्टतम इंटरकनेक्ट की आवश्यकता होती है। एक प्रसिद्ध संस्करण, जिसे प्रायः स्टाइनर ट्री समस्या शब्द के साथ समानार्थी रूप से प्रयोग किया जाता है, ग्राफ़ में स्टाइनर ट्री समस्या है। गैर-ऋणात्मक धार भार और शीर्षों के एक उपसमुच्चय के साथ एक अप्रत्यक्ष ग्राफ को देखते हुए, जिसे प्रायः टर्मिनल के रूप में संदर्भित किया जाता है, रेखांकन में स्टाइनर ट्री समस्या के लिए न्यूनतम वजन के एक पेड़ (ग्राफ सिद्धांत) की आवश्यकता होती है। जिसमें सभी टर्मिनल सम्मिलित हैं (लेकिन अतिरिक्त कोने सम्मिलित हो सकते हैं)और इसके किनारों के कुल वजन को कम करता है। यूक्लिडियन स्टाइनर ट्री समस्या और रेक्टिलिनियर स्टाइनर ट्री इसके और भी प्रसिद्ध संस्करण हैं।

रेखांकन में स्टाइनर ट्री समस्या को दो अन्य प्रसिद्ध दहनशील अनुकूलन समस्याओं के सामान्यीकरण के रूप में देखा जा सकता है: (गैर-नकारात्मक) सबसे छोटी पथ समस्या और न्यूनतम फैले हुए पेड़। यदि ग्राफ में स्टाइनर ट्री की समस्या में ठीक दो टर्मिनल हैं, तो यह सबसे छोटा रास्ता खोजने के लिए कम हो जाता है। यदि, दूसरी ओर, सभी कोने टर्मिनल हैं, तो ग्राफ़ में स्टाइनर ट्री समस्या न्यूनतम फैले हुए ट्री के बराबर है। हालाँकि, जबकि गैर-नकारात्मक सबसे छोटा रास्ता और न्यूनतम फैले हुए पेड़ की समस्या बहुपद समय में हल करने योग्य हैं, रेखांकन में स्टीनर पेड़ की समस्या की निर्णय समस्या एनपी-पूर्ण है (जिसका अर्थ है कि अनुकूलन संस्करण एनपी-कठोरता है। एनपी- मुश्किल); वास्तव में, निर्णय संस्करण कार्प की 21 एनपी-पूर्ण समस्याओं में से एक था। कार्प की मूल 21 एनपी-पूर्ण समस्याएं। रेखांकन में स्टाइनर ट्री समस्या में विद्युत नेटवर्क लेआउट या नेटवर्क डिजाइन में अनुप्रयोग हैं। हालांकि, व्यावहारिक अनुप्रयोगों में प्रायः विविधताओं की आवश्यकता होती है, जिससे स्टाइनर ट्री समस्या वेरिएंट की भीड़ बढ़ जाती है।

स्टाइनर ट्री समस्या के अधिकांश संस्करण एनपी-हार्ड हैं, लेकिन कुछ प्रतिबंधित मामलों को बहुपद समय में हल किया जा सकता है। निराशावादी सबसे खराब स्थिति जटिलता के बावजूद, कई स्टाइनर ट्री प्रॉब्लम वैरिएंट, जिसमें ग्राफ़ में स्टाइनर ट्री प्रॉब्लम और रेक्टिलाइनियर स्टाइनर ट्री प्रॉब्लम सम्मिलित हैं, व्यवहार में कुशलता से हल किए जा सकते हैं, यहाँ तक कि बड़े पैमाने की वास्तविक दुनिया की समस्याओं के लिए भी।

यूक्लिडियन स्टाइनर ट्री

Minimum Steiner trees of vertices of regular polygons with N = 3 to 8 sides. The lowest network length L for N > 5 is the circumference less one side. Squares represent Steiner points.

मूल समस्या को उस रूप में कहा गया था जिसे यूक्लिडियन स्टाइनर ट्री समस्या या ज्यामितीय स्टाइनर ट्री समस्या के रूप में जाना जाता है: प्लेन (ज्यामिति) में 'एन' अंक दिए गए हैं, लक्ष्य उन्हें न्यूनतम कुल लंबाई की रेखाओं से जोड़ना है इस प्रकार कि किन्हीं भी दो बिंदुओं को या तो सीधे रेखाखंडों द्वारा या अन्य बिंदुओं (ज्यामिति) और रेखाखंडों के माध्यम से आपस में जोड़ा जा सकता है। यह दिखाया जा सकता है कि कनेक्टिंग रेखा खंड एंडपॉइंट्स को छोड़कर एक दूसरे को नहीं काटते हैं और एक पेड़ बनाते हैं, इसलिए समस्या का नाम।

N = 3 के लिए समस्या पर लंबे समय से विचार किया गया है, और जल्दी से न्यूनतम कुल लंबाई के सभी N दिए गए बिंदुओं से जुड़े एक हब के साथ एक तारा (ग्राफ़ सिद्धांत) खोजने की समस्या तक बढ़ा दिया गया है . हालांकि, हालांकि स्टाइनर ट्री की पूरी समस्या कार्ल फ्रेडरिक गॉस के एक पत्र में तैयार की गई थी, इसका पहला गंभीर उपचार 1934 में वोजटेक जार्निक द्वारा चेक में लिखे गए एक पेपर में था और Miloš Kössler. इस पेपर को लंबे समय तक अनदेखा किया गया था, लेकिन इसमें पहले से ही स्टाइनर पेड़ों के लगभग सभी सामान्य गुण सम्मिलित हैं, जिन्हें बाद में अन्य शोधकर्ताओं के लिए जिम्मेदार ठहराया गया था, जिसमें विमान से लेकर उच्च आयामों तक की समस्या का सामान्यीकरण सम्मिलित था। यूक्लिडियन स्टाइनर समस्या के लिए, ग्राफ़ में जोड़े गए बिंदु (स्टाइनर पॉइंट (कम्प्यूटेशनल ज्योमेट्री)) में तीन की डिग्री (ग्राफ़ सिद्धांत) होना चाहिए, और इस तरह के बिंदु पर तीन किनारों की घटना को तीन 120 डिग्री कोण बनाना चाहिए (फर्मेट बिंदु देखें) . यह इस प्रकार है कि एक स्टाइनर पेड़ के पास अधिकतम स्टाइनर बिंदु N − 2 हो सकते हैं, जहां N दिए गए बिंदुओं की प्रारंभिक संख्या है।

N = 3 के लिए दो संभावित स्थितियाँ हैं: यदि दिए गए बिंदुओं से बने त्रिभुज के सभी कोण 120 डिग्री से कम हैं, तो समाधान फर्मेट बिंदु पर स्थित स्टाइनर बिंदु द्वारा दिया जाता है; अन्यथा समाधान त्रिभुज की दो भुजाओं द्वारा दिया जाता है जो 120 या अधिक डिग्री वाले कोण पर मिलती हैं।

सामान्य एन के लिए, यूक्लिडियन स्टाइनर पेड़ की समस्या एनपी कठिन है, और इसलिए यह ज्ञात नहीं है कि बहुपद-समय एल्गोरिदम का उपयोग करके एक अनुकूलन समस्या पाई जा सकती है या नहीं। हालांकि, यूक्लिडियन स्टाइनर पेड़ों के लिए एक बहुपद-समय सन्निकटन योजना (PTAS) है, अर्थात, बहुपद समय में निकट-इष्टतम समाधान पाया जा सकता है। यह ज्ञात नहीं है कि क्या यूक्लिडियन स्टाइनर ट्री समस्या एनपी-पूर्ण है, क्योंकि जटिलता वर्ग एनपी की सदस्यता ज्ञात नहीं है।

रेक्टिलाइनियर स्टाइनर ट्री

Main article: Rectilinear Steiner tree

रेक्टिलाइनियर स्टाइनर ट्री समस्या प्लेन में ज्यामितीय स्टाइनर ट्री समस्या का एक रूप है, जिसमें यूक्लिडियन दूरी को रेक्टिलाइनियर दूरी से बदल दिया जाता है। समस्या इलेक्ट्रॉनिक डिजाइन स्वचालन के भौतिक डिज़ाइन (इलेक्ट्रॉनिक्स) में उत्पन्न होती है। वीएलएसआई सर्किट में, वायर रूटिंग उन तारों द्वारा की जाती है जो प्रायः डिजाइन नियमों द्वारा केवल ऊर्ध्वाधर और क्षैतिज दिशाओं में चलने के लिए विवश होते हैं, इसलिए सीधी रेखा दूरी ट्री समस्या का उपयोग दो से अधिक टर्मिनलों वाले जालों के रूटिंग को मॉडल करने के लिए किया जा सकता है।

स्टाइनर ट्री ग्राफ और वेरिएंट में

भारित रेखांकन के संदर्भ में स्टीनर के पेड़ों का व्यापक अध्ययन किया गया है। प्रोटोटाइप, यकीनन, रेखांकन में स्टाइनर ट्री समस्या है। मान लें कि G = (V, E) गैर-ऋणात्मक किनारे भार c के साथ एक अप्रत्यक्ष ग्राफ़ है और S ⊆ V शीर्षों का एक उपसमुच्चय है, टर्मिनल कहलाते हैं। स्टाइनर का पेड़ 'जी' में एक पेड़ है जो 'एस' तक फैला हुआ है। समस्या के दो संस्करण हैं: स्टाइनर ट्री से संबंधित अनुकूलन समस्या में, कार्य एक न्यूनतम वजन वाले स्टाइनर ट्री को खोजना है; निर्णय की समस्या में किनारे का वजन पूर्णांक होता है और कार्य यह निर्धारित करना है कि क्या स्टाइनर का पेड़ मौजूद है जिसका कुल वजन पूर्वनिर्धारित प्राकृतिक संख्या k से अधिक नहीं है। निर्णय समस्या कार्प की 21 एनपी-पूर्ण समस्याओं में से एक है; इसलिए अनुकूलन समस्या एनपी-कठिन है। रेखांकन में स्टाइनर ट्री समस्याओं को अनुसंधान और उद्योग में विभिन्न समस्याओं पर लागू किया जाता है, मल्टीकास्ट रूटिंग सहित और जैव सूचना विज्ञान। इस समस्या का एक विशेष मामला तब होता है जब G एक पूर्ण ग्राफ़ होता है, प्रत्येक शीर्ष v ∈ V एक मीट्रिक स्थान में एक बिंदु के अनुरूप होता है, और प्रत्येक e ∈ E के लिए किनारों का भार w(e) अंतरिक्ष में दूरियों के अनुरूप होता है। अन्यथा रखें, किनारे का भार त्रिकोण असमानता को संतुष्ट करता है। इस संस्करण को 'मीट्रिक स्टाइनर ट्री प्रॉब्लम' के रूप में जाना जाता है। (गैर-मीट्रिक) स्टाइनर ट्री समस्या के एक उदाहरण को देखते हुए, हम इसे बहुपद समय में मीट्रिक स्टाइनर ट्री समस्या के समतुल्य उदाहरण में बदल सकते हैं; परिवर्तन सन्निकटन कारक को बरकरार रखता है।

जबकि यूक्लिडियन संस्करण एक पीटीएएस को स्वीकार करता है, यह ज्ञात है कि मीट्रिक स्टाइनर ट्री समस्या एपीएक्स-पूर्ण है, अर्थात, जब तक पी = एनपी नहीं है, तब तक सन्निकटन अनुपात प्राप्त करना असंभव है जो बहुपद समय में मनमाने ढंग से 1 के करीब हैं। वहाँ एक बहुपद समय एल्गोरिथ्म है कि अनुमानित एल्गोरिथ्म न्यूनतम स्टाइनर पेड़ के एक कारक के भीतर है $\ln(4)+\varepsilon \approx 1.386$; हालांकि, एक कारक के भीतर अनुमानित $96/95\approx 1.0105$ एनपी-हार्ड है। दूरियों 1 और 2 के साथ स्टाइनर ट्री समस्या के प्रतिबंधित मामले के लिए, एक 1.25-सन्निकटन एल्गोरिथम ज्ञात है। करपिंस्की और अलेक्जेंडर ज़ेलिकोवस्की ने स्टाइनर ट्री समस्याओं के घने उदाहरणों के लिए पीटीएएस का निर्माण किया।

ग्राफ़ समस्या के एक विशेष मामले में, अर्ध-द्विपक्षीय ग्राफ़ के लिए स्टाइनर ट्री समस्या, S को G में प्रत्येक किनारे के कम से कम एक समापन बिंदु को सम्मिलित करना आवश्यक है।

उच्च आयामों और विभिन्न सतहों पर स्टाइनर ट्री समस्या की भी जांच की गई है। स्टाइनर मिनिमल ट्री को खोजने के लिए एल्गोरिद्म स्फेयर, टोरस, प्रक्षेपी विमान , चौड़े और संकरे शंकु और अन्य पर पाए गए हैं।

स्टाइनर ट्री समस्या के अन्य सामान्यीकरण हैं के-एज-कनेक्टेड स्टाइनर नेटवर्क प्रॉब्लम और के-वर्टेक्स-कनेक्टेड स्टाइनर नेटवर्क प्रॉब्लम, जहां लक्ष्य के-एज-कनेक्टेड ग्राफ को खोजना है। k-एज-कनेक्टेड ग्राफ़ या k-वर्टेक्स-कनेक्टेड ग्राफ़|k-वरटेक्स-कनेक्टेड ग्राफ़ बजाय किसी कनेक्टेड ग्राफ़ के। एक और अच्छी तरह से अध्ययन किया सामान्यीकरण उत्तरजीविता नेटवर्क डिजाइन समस्या (एसएनडीपी) है जहां कार्य प्रत्येक शीर्ष जोड़ी को एक निश्चित संख्या (संभवतः 0) के किनारे- या शीर्ष-विच्छेद पथों से जोड़ना है।

मीट्रिक रिक्त स्थान की सामान्य सेटिंग में स्टाइनर समस्या भी बताई गई है और संभवत: असीम रूप से कई बिंदुओं के लिए।

स्टाइनर ट्री का अनुमान लगाना

सामान्य ग्राफ स्टाइनर ट्री समस्या को टर्मिनल वर्टिकल द्वारा प्रेरित ग्राफ के मीट्रिक क्लोजर के सबग्राफ के न्यूनतम फैले हुए पेड़ की गणना करके अनुमानित किया जा सकता है, जैसा कि 1981 में कोउ एट अल द्वारा पहली बार प्रकाशित किया गया था। ग्राफ़ G का मेट्रिक क्लोजर एक पूरा ग्राफ़ है जिसमें प्रत्येक किनारे को G में नोड्स के बीच सबसे छोटी पथ दूरी द्वारा भारित किया जाता है। यह एल्गोरिद्म एक पेड़ का निर्माण करता है जिसका वज़न 2 − 2/t फ़ैक्टर के भार के भीतर होता है इष्टतम स्टाइनर ट्री जहां टी इष्टतम स्टाइनर ट्री में पत्तियों की संख्या है; यह इष्टतम स्टाइनर ट्री पर यात्रा विक्रेता के दौरे पर विचार करके सिद्ध किया जा सकता है। यह अनुमानित समाधान O(|S| |V|²) समय जटिलता में संगणनीय है #बहुपद समय सबसे पहले शॉर्टेस्ट पाथ प्रॉब्लम को हल करके #ऑल-पेयर शॉर्टेस्ट पाथ|ऑल-पेयर शॉर्टेस्ट पाथ प्रॉब्लम को मेट्रिक क्लोजर की गणना करने के लिए, फिर हल करके न्यूनतम फैले पेड़।

1980 में ताकाहाशी और मात्सुयामा द्वारा रेखांकन में स्टीनर के पेड़ को अनुमानित करने के लिए एक और लोकप्रिय एल्गोरिथ्म प्रकाशित किया गया था। उनका समाधान मनमाने ढंग से शीर्ष से शुरू करके स्टाइनर पेड़ को बढ़ाता है, और बार-बार पेड़ से सबसे छोटा पथ एस में निकटतम शीर्ष तक जोड़ता है जिसे अभी तक जोड़ा नहीं गया है। इस एल्गोरिथ्म में O(|S| |V|²) चलने का समय भी है, और एक पेड़ का उत्पादन करता है जिसका वजन 2 − 2/|S| के भीतर है। इष्टतम का।

1986 में, वू एट अल। सभी जोड़ियों के सबसे छोटे रास्तों की पूर्व संगणना से बचकर रनिंग टाइम में नाटकीय रूप से सुधार हुआ। इसके बजाय, वे |S| पेड़ों को अलग करना, और उन्हें एक साथ बढ़ाना एक चौड़ाई-पहली खोज का उपयोग करते हुए दिज्क्स्ट्रा के एल्गोरिथ्म जैसा दिखता है लेकिन कई प्रारंभिक कोने से शुरू होता है। जब खोज एक शीर्ष का सामना करती है जो वर्तमान पेड़ से संबंधित नहीं है, तो दो पेड़ एक में विलय हो जाते हैं। यह प्रक्रिया तब तक दोहराई जाती है जब तक कि केवल एक पेड़ शेष न रह जाए। प्राथमिकता कतार को लागू करने के लिए हीप (डेटा संरचना) का उपयोग करके और एक अलग-सेट डेटा संरचना का उपयोग करके यह ट्रैक करने के लिए कि प्रत्येक दौरा किया गया शीर्ष किस पेड़ से संबंधित है, यह एल्गोरिथम O(|E| log |V|) चलने का समय प्राप्त करता है, हालांकि यह नहीं करता है कोउ एट अल से 2 − 2/t लागत अनुपात में सुधार।

कागजात की एक श्रृंखला ने सन्निकटन अनुपात के साथ न्यूनतम स्टाइनर ट्री समस्या के लिए सन्निकटन एल्गोरिदम प्रदान किया जो 2 − 2/t अनुपात में सुधार हुआ। यह अनुक्रम 2000 में रॉबिन्स और ज़ेलिकोव्स्की के एल्गोरिदम के साथ समाप्त हुआ, जिसने न्यूनतम लागत टर्मिनल फैले पेड़ पर क्रमिक रूप से सुधार करके 1.55 के अनुपात में सुधार किया। हाल ही में, हालांकि, बायर्का एट अल। एक साबित हुआ $\ln(4)+\varepsilon \leq 1.39$ एक रेखीय प्रोग्रामिंग विश्राम और पुनरावृत्त, यादृच्छिक गोलाई नामक तकनीक का उपयोग करके सन्निकटन।

== स्टाइनर ट्री == की पैरामीटरयुक्त जटिलता

सामान्य ग्राफ स्टाइनर ट्री समस्या को ड्रेफस-वैगनर एल्गोरिथम द्वारा पैरामीटर के रूप में टर्मिनलों की संख्या के साथ पैरामीटरयुक्त जटिलता#एफपीटी|फिक्स्ड-पैरामीटर ट्रैक्टेबल के रूप में जाना जाता है। ड्रेफस-वैगनर एल्गोरिथम का रनिंग टाइम है $3^{|S|}{\text{poly}}(n)$, कहाँ $n$ ग्राफ के शीर्षों की संख्या है और $S$ टर्मिनलों का सेट है। तेज़ एल्गोरिदम मौजूद हैं, चल रहे हैं $c^{|S|}{\text{poly}}(n)$ किसी के लिए समय $c>2$ या, छोटे वजन के मामले में, $2^{|S|}{\text{poly}}(n)W$ समय, कहाँ $W$ किसी किनारे का अधिकतम वजन है। पूर्वोक्त एल्गोरिदम का एक नुकसान यह है कि वे अंतरिक्ष जटिलता का उपयोग करते हैं; इसमें बहुपद-अंतरिक्ष एल्गोरिदम चल रहे हैं $2^{|S|}{\text{poly}}(n)W$ समय और $(7.97)^{|S|}{\text{poly}}(n)\log W$ समय।

यह ज्ञात है कि सामान्य ग्राफ़ स्टीनर ट्री समस्या में एक पैरामिट्रीकृत एल्गोरिथम नहीं चल रहा है $2^{\epsilon t}{\text{poly}}(n)$ किसी के लिए समय $\epsilon <1$, कहाँ $t$ इष्टतम स्टाइनर ट्री के किनारों की संख्या है, जब तक कि सेट कवर समस्या में एल्गोरिदम चल रहा हो $2^{\epsilon n}{\text{poly}}(m)$ कुछ के लिए समय $\epsilon <1$, कहाँ $n$ और $m$ सेट कवर समस्या के उदाहरण के क्रमशः तत्वों की संख्या और सेट की संख्या हैं। इसके अलावा, यह ज्ञात है कि समस्या तब तक कर्नेलीकरण को स्वीकार नहीं करती है जब तक ${\text{coNP}}\subseteq {\text{NP/poly}}$, यहां तक ​​​​कि इष्टतम स्टाइनर पेड़ के किनारों की संख्या के आधार पर और यदि सभी किनारों का वजन 1 है।

स्टाइनर ट्री का पैरामीटरेटेड सन्निकटन

जबकि ग्राफ स्टाइनर ट्री समस्या तब तक कर्नेलीकरण को स्वीकार नहीं करती है जब तक ${\text{coNP}}\subseteq {\text{NP/poly}}$ टर्मिनलों की संख्या द्वारा पैरामीटरीकृत, यह एक पैरामीटरयुक्त सन्निकटन एल्गोरिथम#अनुमानित कर्नेलाइज़ेशन|बहुपद-आकार की अनुमानित कर्नेलाइज़ेशन योजना (PSAKS) को स्वीकार करता है: किसी के लिए $\varepsilon >0$ एक बहुपद-आकार के कर्नेल की गणना करना संभव है, जो केवल a खोता है $1+\varepsilon$ समाधान की गुणवत्ता में कारक। संख्या द्वारा ग्राफ स्टाइनर ट्री समस्या का पैरामीटरकरण करते समय $p$ इष्टतम समाधान में गैर-टर्मिनलों (स्टाइनर वर्टिस) की, समस्या है Parameterized Complex#W hierarchy|W[1]-hard (टर्मिनलों की संख्या द्वारा पैरामीटरकरण के विपरीत, जैसा कि ऊपर उल्लेख किया गया है)। साथ ही समस्या एपीएक्स-पूर्ण है और इस प्रकार पी = एनपी तक, बहुपद-समय अनुमान योजना को स्वीकार नहीं करता है। हालाँकि, एक पैरामीटरयुक्त सन्निकटन एल्गोरिथ्म मौजूद है, जो किसी के लिए भी है $\varepsilon >0$ ए की गणना करता है $(1+\varepsilon )$- सन्निकटन में $2^{O(p^{2}/\varepsilon ^{4})}n^{O(1)}$ समय। इस मानकीकरण के लिए एक PSAKS भी मौजूद है।

स्टाइनर अनुपात

स्टाइनर अनुपात यूक्लिडियन विमान में बिंदुओं के एक सेट के लिए न्यूनतम फैले हुए पेड़ की न्यूनतम लंबाई के न्यूनतम स्टाइनर पेड़ के अनुपात का सर्वोच्च है।

यूक्लिडियन स्टाइनर ट्री समस्या में, स्टाइनर अनुपात होने का अनुमान लगाया गया है ${\tfrac {2}{\sqrt {3}}}\approx 1.1547$, वह अनुपात जो त्रिभुज की दो भुजाओं का उपयोग करने वाले एक फैले हुए वृक्ष और एक स्टाइनर वृक्ष के साथ एक समबाहु त्रिभुज में तीन बिंदुओं द्वारा प्राप्त किया जाता है जो त्रिभुज के केन्द्रक के माध्यम से बिंदुओं को जोड़ता है। सबूत के पहले के दावों के बावजूद, अनुमान अभी भी खुला है। समस्या के लिए सबसे व्यापक रूप से स्वीकृत ऊपरी सीमा 1.2134 है Chung & Graham (1985).

रेक्टिलाइनियर स्टाइनर ट्री समस्या के लिए, स्टाइनर अनुपात ठीक है ${\tfrac {3}{2}}$, वह अनुपात जो वर्ग के तीन पक्षों का उपयोग करने वाले फैले हुए पेड़ और एक स्टाइनर पेड़ के साथ वर्ग में चार बिंदुओं से प्राप्त होता है जो वर्ग के केंद्र के माध्यम से बिंदुओं को जोड़ता है। अधिक सटीक, के लिए $L_{1}$ दूरी पर वर्ग झुका होना चाहिए $45^{\circ }$ समन्वय अक्षों के संबंध में, जबकि के लिए $L_{\infty }$ दूरी वर्ग अक्ष-संरेखित होना चाहिए।

यह भी देखें

• अपारदर्शी वन समस्या
• ट्रैवलिंग सेल्समैन की समस्या

संदर्भ

• Berman, Piotr; Karpinski, Marek; Zelikovsky, Alexander (2009). "1.25-approximation algorithm for Steiner tree problem with distances 1 and 2". Algorithms and Data Structures: 11th International Symposium, WADS 2009, Banff, Canada, August 21–23, 2009, Proceedings. Lecture Notes in Computer Science. Vol. 5664. pp. 86–97. arXiv:0810.1851. doi:10.1007/978-3-642-03367-4_8.
• Bern, Marshall W.; Graham, Ronald L. (1989). "The shortest-network problem". Scientific American. 260 (1): 84–89. Bibcode:1989SciAm.260a..84B. doi:10.1038/scientificamerican0189-84.
• Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko (2007). "Fourier Meets Möbius: Fast Subset Convolution". Proceedings of the 39th ACM Symposium on Theory of Computing. pp. 67–74. arXiv:cs/0611101. doi:10.1145/1250790.1250801.
• Byrka, J.; Grandoni, F.; Rothvoß, T.; Sanita, L. (2010). "An improved LP-based approximation for Steiner tree". Proceedings of the 42nd ACM Symposium on Theory of Computing. pp. 583–592. CiteSeerX 10.1.1.177.3565. doi:10.1145/1806689.1806769.
• Chlebík, Miroslav; Chlebíková, Janka (2008). "The Steiner tree problem on graphs: Inapproximability results". Theoretical Computer Science. 406 (3): 207–214. doi:10.1016/j.tcs.2008.06.046.
• Chung, F. R. K.; Graham, R. L. (1985). "A new bound for Euclidean Steiner minimal trees". Discrete geometry and convexity (New York, 1982). Annals of the New York Academy of Science. Vol. 440. New York: New York Academy of Science. pp. 328–346. Bibcode:1985NYASA.440..328C. doi:10.1111/j.1749-6632.1985.tb14564.x. MR 0809217.
• Cieslik, Dietmar (1998). Steiner Minimal Trees. p. 319. ISBN 0-7923-4983-0.
• Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (2000). "Minimum geometric Steiner tree". A Compendium of NP Optimization Problems.
• Cygan, Marek; Dell, Holger; Lokshtanov, Daniel; Marx, Dániel; Nederlof, Jesper; Okamoto, Yoshio; Paturi, Ramamohan; Saurabh, Saket; Wahlström, Magnus (2016). "On Problems as Hard as CNF-SAT". ACM Transactions on Algorithms. 12 (3): 41:1–41:24. doi:10.1145/2925416. S2CID 7320634.
• Dom, Michael; Lokshtanov, Daniel; Saurabh, Saket (2014). "Kernelization Lower Bounds Through Colors and IDs". ACM Transactions on Algorithms. 11 (2): 13:1–13:20. doi:10.1145/2650261. S2CID 13570734.
• Dreyfus, S.E.; Wagner, R.A. (1971). "The Steiner problem in graphs". Networks. 1 (3): 195–207. doi:10.1002/net.3230010302.
• Fomin, Fedor V.; Kaski, Petteri; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket (2015). "Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree". Automata, Languages, and Programming – 42nd International Colloquium, ICALP 2015, Proceedings, Part I. pp. 494–505. doi:10.1007/978-3-662-47672-7_40.
• Fuchs, Benjamin; Kern, Walter; Mölle, Daniel; Richter, Stefan; Rossmanith, Peter; Wang, Xinhui (2007). "Dynamic Programming for Minimum Steiner Trees" (PDF). Theory of Computing Systems. 41 (3): 493–500. doi:10.1007/s00224-007-1324-4. S2CID 7478978.
• Ganley, Joseph L. (2004). "Steiner ratio". In Black, Paul E. (ed.). Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Retrieved 24 May 2012.
• Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5, pp. 208–209, problems ND12 and ND13.
• Hwang, F. K. (1976). "On Steiner minimal trees with rectilinear distance". SIAM Journal on Applied Mathematics. 30 (1): 104–114. doi:10.1137/0130013.
• Hwang, F. K.; Richards, D. S.; Winter, P. (1992). The Steiner Tree Problem. Annals of Discrete Mathematics. Vol. 53. North-Holland: Elsevier. ISBN 0-444-89098-X.
• Ivanov, Alexander; Tuzhilin, Alexey (1994). Minimal Networks: The Steiner Problem and Its Generalizations. N.W., Boca Raton, Florida: CRC Press. ISBN 978-0-8493-8642-8.
• Ivanov, Alexander; Tuzhilin, Alexey (2000). Branching solutions to one-dimensional variational problems. Singapore-New Jersey-London-Hong Kong: World Scientific. ISBN 978-981-02-4060-8.
• Ivanov, Alexander; Tuzhilin, Alexey (2003). Extreme Networks Theory (in Russian). Moscow-Izhevsk: Institute of Computer Investigations. ISBN 5-93972-292-X.{{cite book}}: CS1 maint: unrecognized language (link)
• Ivanov, Alexander; Tuzhilin, Alexey (2012). "The Steiner ratio Gilbert–Pollak conjecture is still open: Clarification statement". Algorithmica. 62 (1–2): 630–632. doi:10.1007/s00453-011-9508-3. S2CID 7486839.
• Ivanov, Alexander; Tuzhilin, Alexey (2015). "Branched coverings and Steiner ratio". International Transactions in Operational Research. 23 (5): 875–882. arXiv:1412.5433. doi:10.1111/itor.12182. S2CID 3386263.
• Juhl, D.; Warme, D.M.; Winter, P.; Zachariasen, M. (January 2018). "The GeoSteiner Software Package for computing Steiner trees in the plane: an updated computational study". Math. Prog. Comp. 10 (4): 487–532. doi:10.1007/s12532-018-0135-8.
• Rehfeldt, D.; Koch, T. (February 2023). "Implications, conflicts, and reductions for Steiner trees". Math. Prog. 197 (2): 903–966. doi:10.1007/s10107-021-01757-5.
• Karpinski, Marek; Zelikovsky, Alexander (1998). "Approximating dense cases of covering problems". Proceedings of the DIMACS Workshop on Network Design: Connectivity and Facilities Location. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. Vol. 40. American Mathematical Society. pp. 169–178.
• Korte, Bernhard; Vygen, Jens (2006). "Section 20.1". Combinatorial Optimization: Theory and Algorithms (3rd ed.). Springer. ISBN 3-540-25684-9.
• Kou, L.; Markowsky, G.; Berman, L. (1 June 1981). "A fast algorithm for Steiner trees". Acta Informatica. 15 (2): 141–145. doi:10.1007/BF00288961. S2CID 21057232.
• Levin, A. Yu. (1971). "Algorithm for the shortest connection of a group of graph vertices". Soviet Mathematics Doklady. 12: 1477–1481.
• Lokshtanov, Daniel; Nederlof, Jesper (2010). "Saving space by algebraization". Proceedings of the 42nd ACM Symposium on Theory of Computing. pp. 321–330. doi:10.1145/1806689.1806735.
• Paolini, E.; Stepanov, E. (2012). "Existence and regularity results for the Steiner problem" (PDF). Calc. Var. Partial Diff. Equations. 46 (3–4): 837–860. doi:10.1007/s00526-012-0505-4. hdl:2158/600141. S2CID 55793499.
• Robins, Gabriel; Zelikovsky, Alexander (2000). "Improved Steiner Tree Approximation in Graphs". Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '00). Philadelphia, PA, USA: Society for Industrial and Applied Mathematics. pp. 770–779. ISBN 0-89871-453-2.
• Sherwani, Naveed A. (1993). Algorithms for VLSI Physical Design Automation. Kluwer Academic Publishers. ISBN 9781475722192.
• Smith, J. M.; Winter, P. (1995). "Computational geometry and topological network design". In Du, Ding-Zhu; Hwang, Frank (eds.). Computing in Euclidean geometry. Lecture Notes Series on Computing. Vol. 4 (2nd ed.). River Edge, NJ: World Scientific Publishing Co. pp. 351–451. ISBN 981-02-1876-1.
• Takahashi, Hiromitsu; Matsuyama, Akira (1980). "An approximate solution for the Steiner problem in graphs". Math. Japonica. 24 (6): 573–577.
• Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. ISBN 3-540-65367-8.
• Wu, Bang Ye; Chao, Kun-Mao (2004). "Chapter 7". Spanning Trees and Optimization Problems. Chapman & Hall/CRC. ISBN 1-58488-436-3.
• Wu, Y. F.; Widmayer, P.; Wong, C. K. (May 1986). "A faster approximation algorithm for the Steiner problem in graphs". Acta Informatica. 23 (2): 223–229. doi:10.1007/bf00289500. S2CID 7772232.

बाहरी संबंध

• GeoSteiner (Software for solving Euclidean and rectilinear Steiner tree problems; source available, free for non-commercial use)
• SCIP-Jack (Software for solving the Steiner tree problem in graphs and 14 variants, e.g., prize-collecting Steiner tree problem; free for non-commercial use)
• Fortran subroutine for finding the Steiner vertex of a triangle (i.e., Fermat point), its distances from the triangle vertices, and the relative vertex weights.
• Phylomurka (Solver for small-scale Steiner tree problems in graphs)
• https://www.youtube.com/watch?v=PI6rAOWu-Og (Movie: solving the Steiner tree problem with water and soap)
• Noormohammadpour, Mohammad; Raghavendra, Cauligi S.; Rao, Sriram; Kandula, Srikanth (2017), "Using Steiner Trees to Minimize Average Completion Times of Bulk Data Transfers", DCCast: Efficient Point to Multipoint Transfers Across Datacenters, USENIX Association, arXiv:1707.02096
• Hazewinkel, M. (2001) [1994], "Steiner tree problem", Encyclopedia of Mathematics, EMS Press
• M. Hauptmann, M. Karpinski (2013): A Compendium on Steiner Tree Problems