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

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

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

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

रेखांकन में स्टाइनर ट्री समस्या को दो अन्य प्रसिद्ध संयोजी अनुकूलन समस्याओं के सामान्यीकरण के रूप में देखा जा सकता है: (गैर-नकारात्मक) सबसे छोटी पथ समस्या और न्यूनतम संयोजी ट्री समस्या। यदि ग्राफ में स्टाइनर ट्री की समस्या में ठीक दो टर्मिनल हैं, तो यह सबसे छोटा रास्ता खोजने के लिए कम हो जाता है। यदि, दूसरी ओर, सभी कोने टर्मिनल हैं, तो ग्राफ़ में स्टाइनर ट्री समस्या न्यूनतम फैले हुए ट्री के बराबर है। हालाँकि, जबकि गैर-नकारात्मक सबसे छोटा रास्ता और न्यूनतम फैले हुए ट्री की समस्या बहुपद समय में हल करने योग्य हैं, स्टाइनर ट्री की समस्या के लिए ऐसा कोई समाधान ज्ञात नहीं है। इसका निर्णय संस्करण, यह पूछने पर कि क्या किसी दिए गए इनपुट में किसी दिए गए थ्रेसहोल्ड से कम वजन का ट्री है, एनपी-पूर्ण है, जिसका अर्थ है कि अनुकूलन संस्करण, किसी दिए गए ग्राफ में न्यूनतम वजन वाले ट्री की मांग करना, एनपी-कठोर है। वस्तुत:, निर्णय संस्करण कार्प की 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 में वोजटेक जार्निक और मिलोस कोस्लर [सीएस] द्वारा चेक में लिखे गए एक पेपर में था। इस पेपर को लंबे समय तक अनदेखा किया गया था, लेकिन इसमें पहले से ही ''स्टाइनर ट्रीज के लगभग सभी सामान्य गुण'' सम्मिलित हैं, जिन्हें बाद में अन्य शोधकर्ताओं के लिए जिम्मेदार ठहराया गया था, जिसमें समतल से लेकर उच्च आयामों तक की समस्या का सामान्यीकरण सम्मिलित है।

यूक्लिडियन स्टाइनर समस्या के लिए, ग्राफ़ में जोड़े गए बिंदुओं (स्टाइनर पॉइंट) में तीन की डिग्री होनी चाहिए, और इस तरह के बिंदु पर तीन किनारों की घटना को तीन 120 डिग्री कोण बनाना चाहिए (फर्मेट बिंदु देखें)। यह इस प्रकार है कि एक स्टाइनर ट्री के पास अधिकतम स्टाइनर बिंदु N − 2 हो सकते हैं, जहां N दिए गए बिंदुओं की प्रारंभिक संख्या है।

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

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

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

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

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

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

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

इस समस्या का एक विशेष स्थिति तब होती है जब G एक पूर्ण ग्राफ़ होता है, प्रत्येक शीर्ष v ∈ V एक मीट्रिक स्थान में एक बिंदु के अनुरूप होता है, और प्रत्येक e ∈ E के लिए किनारों का भार w(e) रिक्त स्थान में दूरियों के अनुरूप होता है। अन्यथा रखें, किनारे का भार त्रिकोण असमानता को संतुष्ट करता है। इस संस्करण को 'मीट्रिक स्टाइनर ट्री प्रॉब्लम' के रूप में जाना जाता है। (गैर-मीट्रिक) स्टाइनर ट्री समस्या के एक उदाहरण को देखते हुए, हम इसे बहुपद समय में मीट्रिक स्टाइनर ट्री समस्या के समतुल्य उदाहरण में बदल सकते हैं; परिवर्तन सन्निकटन फैक्टर को बरकरार रखता है।

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

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

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

स्टाइनर ट्री समस्या के अन्य सामान्यीकरण के-एज-कनेक्टेड स्टाइनर नेटवर्क प्रॉब्लम और के-वर्टेक्स-कनेक्टेड स्टाइनर नेटवर्क प्रॉब्लम हैं, जहां लक्ष्य किसी कनेक्टेड ग्राफ़ के बजाय के-एज-कनेक्टेड ग्राफ या 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$ समय चल रहे हैं।

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

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

जबकि ग्राफ स्टाइनर ट्री समस्या तब तक बहुपद कर्नेल को स्वीकार नहीं करती है जब तक ${\text{coNP}}\subseteq {\text{NP/poly}}$ टर्मिनलों की संख्या द्वारा परिचालित हो, यह एक बहुपद-आकार कर्नेलीकरण योजना (PSAKS) को स्वीकार करता है: किसी $\varepsilon >0$ के लिए एक बहुपद-आकार के कर्नेल की गणना करना संभव है, जो केवल a $1+\varepsilon$ फैक्टर समाधान की गुणवत्ता में खोता है।

संख्या द्वारा ग्राफ स्टाइनर ट्री समस्या का पैरामीटरकरण करते समय इष्टतम समाधान में गैर-टर्मिनलों (स्टाइनर वर्टिस) के $p$, समस्या डब्ल्यू [1] -हार्ड है (टर्मिनलों की संख्या के पैरामीटर के विपरीत, जैसा कि ऊपर उल्लेख किया गया है)। साथ ही समस्या एपीएक्स-पूर्ण है और इस प्रकार PTAS को स्वीकार नहीं करती है, जब तक कि P = NP न हो। हालाँकि, एक पैरामीटरयुक्त सन्निकटन एल्गोरिथ्म विद्यमान है, जो किसी के लिए भी है $\varepsilon >0$ ए $(1+\varepsilon )$- सन्निकटन में $2^{O(p^{2}/\varepsilon ^{4})}n^{O(1)}$ समय की गणना करता है। इस मानकीकरण के लिए एक PSAKS भी विद्यमान है।

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

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

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

रेक्टिलाइनियर स्टाइनर ट्री समस्या के लिए, स्टाइनर अनुपात ${\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