ग्रीडी एम्बेडिंग
वितरित कंप्यूटिंग और ज्यामितीय ग्राफ सिद्धांत में, लालची एम्बेडिंग दूरसंचार नेटवर्क के नोड्स को निर्देशांक निर्दिष्ट करने की प्रक्रिया है जिससे कि नेटवर्क के अंदर संदेशों को रूट करने के लिए लालची एल्गोरिदम भौगोलिक रूटिंग का उपयोग करने की अनुमति मिल सके। यद्यपि वायरलेस सेंसर नेटवर्क में उपयोग के लिए लालची एम्बेडिंग का प्रस्ताव किया गया है, जिसमें नोड्स के पास पहले से ही भौतिक स्थान में स्थिति होती है, ये उपस्तिथा स्थिति लालची एम्बेडिंग द्वारा उन्हें दी गई स्थिति से भिन्न हो सकती हैं, जो कुछ स्थितियों में वर्चुअल स्पेस में बिंदु हो सकती हैं उच्च आयाम का, या गैर-यूक्लिडियन ज्यामिति में। इस अर्थ में, लालची एम्बेडिंग को ग्राफ ड्राइंग के रूप के रूप में देखा जा सकता है, जिसमें अमूर्त ग्राफ़ (संचार नेटवर्क) ज्यामितीय स्थान में ग्राफ एम्बेडिंग होता है।
भौतिक निर्देशांक का उपयोग करने के अतिरिक्त, आभासी स्थान में निर्देशांक का उपयोग करके भौगोलिक रूटिंग करने का विचार राव एट अल के कारण है।[1]बाद के विकासों से पता चला है कि प्रत्येक नेटवर्क में अतिशयोक्तिपूर्ण विमान में संक्षिप्त शीर्ष निर्देशांक के साथ लालची एम्बेडिंग होती है, कि बहुफलकीय ग्राफ ़ सहित कुछ ग्राफ़ में यूक्लिडियन विमान में लालची एम्बेडिंग होती है, और यूनिट डिस्क ग्राफ़ में मध्यम आयामों के यूक्लिडियन स्थानों में लालची एम्बेडिंग होती है कम खिंचाव कारक.
परिभाषाएँ
लालची रूटिंग में, स्रोत नोड एस से गंतव्य नोड टी तक संदेश मध्यवर्ती नोड्स के माध्यम से चरणों के अनुक्रम द्वारा अपने गंतव्य तक जाता है, जिनमें से प्रत्येक संदेश को निकटतम नोड पर भेजता है जो टी के करीब है। यदि संदेश मध्यवर्ती नोड x तक पहुंचता है जिसका कोई निकटतम t के करीब नहीं है, तो यह प्रगति नहीं कर सकता है और लालची रूटिंग प्रक्रिया विफल हो जाती है। लालची एम्बेडिंग दिए गए ग्राफ़ को इस संपत्ति के साथ एम्बेड करना है कि इस प्रकार की विफलता असंभव है। इस प्रकार, इसे इस गुण के साथ ग्राफ़ के एम्बेडिंग के रूप में वर्णित किया जा सकता है कि प्रत्येक दो नोड्स x और t के लिए, x का निकटतम y उपस्तिथ होता है जैसे कि d(x,t) > d(y,t), जहां d दर्शाता है एम्बेडेड स्थान में दूरी.[2]
बिना लालची एम्बेडिंग वाले ग्राफ़
प्रत्येक ग्राफ़ में यूक्लिडियन विमान में लालची एम्बेडिंग नहीं होती है; स्टार (ग्राफ सिद्धांत) के द्वारा सरल प्रति उदाहरण दिया गया है1,6, आंतरिक नोड और छह पत्तियों वाला पेड़ (ग्राफ सिद्धांत)।[2] जब भी इस ग्राफ़ को समतल में एम्बेड किया जाता है, तो इसकी कुछ दो पत्तियों को 60 डिग्री या उससे कम का कोण बनाना चाहिए, जिससे यह पता चलता है कि इन दो पत्तियों में से कम से कम का निकटतम दूसरे पत्ते के करीब नहीं है।
उच्च आयामों के यूक्लिडियन स्थानों में, अधिक ग्राफ़ में लालची एम्बेडिंग हो सकती है; उदाहरण के लिए, के1,6 त्रि-आयामी यूक्लिडियन अंतरिक्ष में लालची एम्बेडिंग है, जिसमें तारे का आंतरिक नोड मूल पर है और पत्तियां प्रत्येक समन्वय अक्ष के साथ इकाई की दूरी पर हैं। चूँकि, निश्चित आयाम के प्रत्येक यूक्लिडियन स्थान के लिए, ऐसे ग्राफ़ होते हैं जिन्हें लालच से एम्बेड नहीं किया जा सकता है: जब भी संख्या n अंतरिक्ष की चुंबन संख्या समस्या से अधिक होती है, तो ग्राफ़ K1,n कोई लालची एम्बेडिंग नहीं है.[3]
अतिशयोक्तिपूर्ण और संक्षिप्त एम्बेडिंग
यूक्लिडियन विमान के स्थिति के विपरीत, प्रत्येक नेटवर्क में हाइपरबोलिक विमान में लालची एम्बेडिंग होती है। रॉबर्ट क्लेनबर्ग द्वारा इस परिणाम के मूल प्रमाण में, नोड स्थितियों को उच्च परिशुद्धता के साथ निर्दिष्ट करने की आवश्यकता थी,[4] किन्तु बाद में यह दिखाया गया कि, नेटवर्क के फैले हुए पेड़ के भारी पथ अपघटन का उपयोग करके, प्रति बिंदु बिट्स की केवल लॉगरिदमिक संख्या का उपयोग करके, प्रत्येक नोड को संक्षेप में प्रस्तुत करना संभव है।[3] इसके विपरीत, ऐसे ग्राफ़ उपस्तिथ हैं जिनमें यूक्लिडियन विमान में लालची एम्बेडिंग है, किन्तु जिसके लिए ऐसे किसी भी एम्बेडिंग के लिए प्रत्येक बिंदु के कार्टेशियन निर्देशांक के लिए बिट्स की बहुपद संख्या की आवश्यकता होती है।[5][6]
ग्राफ़ के विशेष वर्ग
पेड़
ट्री का वर्ग (ग्राफ सिद्धांत) जो यूक्लिडियन विमान में लालची एम्बेडिंग को स्वीकार करता है, उसे पूरी तरह से चित्रित किया गया है, और पेड़ का लालची एम्बेडिंग रैखिक समय में पाया जा सकता है जब वह उपस्तिथ होता है।[7]
अधिक सामान्य ग्राफ़ के लिए, कुछ लालची एम्बेडिंग एल्गोरिदम जैसे कि क्लेनबर्ग द्वारा बनाया गया[4] दिए गए ग्राफ़ का स्पैनिंग ट्री ढूंढकर प्रारंभ करें, और फिर स्पैनिंग ट्री का लालची एम्बेडिंग बनाएं। परिणाम आवश्यक रूप से पूरे ग्राफ का लालची एम्बेडिंग भी है। चूँकि, ऐसे ग्राफ़ उपस्तिथ हैं जिनमें यूक्लिडियन विमान में लालची एम्बेडिंग है, किन्तु जिनके लिए किसी भी फैले हुए पेड़ में लालची एम्बेडिंग नहीं है।[8]
तलीय रेखांकन
Does every polyhedral graph have a planar greedy embedding with convex faces?
Papadimitriou & Ratajczak (2005) अनुमान लगाया गया है कि प्रत्येक पॉलीहेड्रल ग्राफ ( के-वर्टेक्स-कनेक्टेड ग्राफ़ | 3-वर्टेक्स-कनेक्टेड समतलीय ग्राफ , या स्टीनिट्ज़ के प्रमेय द्वारा समतुल्य उत्तल पॉलीहेड्रॉन का ग्राफ) में यूक्लिडियन विमान में लालची एम्बेडिंग होती है।[2]कैक्टस ग्राफ़ के गुणों का दोहन करके, Leighton & Moitra (2010) अनुमान सिद्ध हुआ;[8][9]इन ग्राफ़ों की लालची एम्बेडिंग को लघुगणकीय रूप से प्रति समन्वय कई बिट्स के साथ संक्षेप में परिभाषित किया जा सकता है।[10] चूँकि, इस प्रमाण के अनुसार निर्मित लालची एम्बेडिंग आवश्यक रूप से समतल एम्बेडिंग नहीं हैं, क्योंकि उनमें किनारों के जोड़े के बीच क्रॉसिंग सम्मिलित हो सकती है। अधिकतम तलीय रेखांकन के लिए, जिसमें प्रत्येक फलक त्रिभुज है, लालची तलीय एम्बेडिंग को फैरी के प्रमेय के भारित संस्करण में नैस्टर-कुराटोव्स्की-मज़ुरकिविज़ लेम्मा को लागू करके पाया जा सकता है। श्नाइडर के स्ट्रेट-लाइन एम्बेडिंग एल्गोरिदम।[11][12]मजबूत पापादिमित्रीउ-रतज्ज़क अनुमान, कि प्रत्येक बहुफलकीय ग्राफ में तलीय लालची एम्बेडिंग होती है जिसमें सभी चेहरे उत्तल होते हैं, अप्रमाणित रहता है।[13]
यूनिट डिस्क ग्राफ़
वायरलेस सेंसर नेटवर्क जो लालची एम्बेडिंग एल्गोरिदम का लक्ष्य हैं, उन्हें अधिकांशतः यूनिट डिस्क ग्राफ़ के रूप में मॉडल किया जाता है, ग्राफ़ जिसमें प्रत्येक नोड को यूनिट डिस्क के रूप में दर्शाया जाता है और प्रत्येक किनारा गैर-रिक्त चौराहे के साथ डिस्क की जोड़ी से मेल खाता है। ग्राफ़ के इस विशेष वर्ग के लिए, पॉलीलॉगरिदमिक आयाम के यूक्लिडियन स्पेस में संक्षिप्त लालची एम्बेडिंग को ढूंढना संभव है, अतिरिक्त संपत्ति के साथ ग्राफ़ में दूरियों को एम्बेडिंग में दूरियों द्वारा त्रुटिहीन रूप से अनुमानित किया जाता है, जिससे कि लालची रूटिंग द्वारा अपनाए गए पथ हों छोटा।[14]
संदर्भ
- ↑ Rao, Ananth; Ratnasamy, Sylvia; Papadimitriou, Christos H.; Shenker, Scott; Stoica, Ion (2003), "Geographic routing without location information", Proc. 9th ACM Mobile Computing and Networking (MobiCom), pp. 96–108, doi:10.1145/938985.938996.
- ↑ 2.0 2.1 2.2 Papadimitriou, Christos H.; Ratajczak, David (2005), "On a conjecture related to geometric routing", Theoretical Computer Science, 344 (1): 3–14, doi:10.1016/j.tcs.2005.06.022, MR 2178923.
- ↑ 3.0 3.1 Eppstein, D.; Goodrich, M. T. (2011), "Succinct greedy geometric routing using hyperbolic geometry", IEEE Transactions on Computers, 60 (11): 1571–1580, doi:10.1109/TC.2010.257.
- ↑ 4.0 4.1 Kleinberg, R. (2007), "Geographic routing using hyperbolic space", Proc. 26th IEEE International Conference on Computer Communications (INFOCOM 2007), pp. 1902–1909, doi:10.1109/INFCOM.2007.221.
- ↑ Cao, Lei; Strelzoff, A.; Sun, J. Z. (2009), "On succinctness of geometric greedy routing in Euclidean plane", 10th International Symposium on Pervasive Systems, Algorithms, and Networks (ISPAN 2009), pp. 326–331, doi:10.1109/I-SPAN.2009.20.
- ↑ Angelini, Patrizio; Di Battista, Giuseppe; Frati, Fabrizio (2010), "Succinct greedy drawings do not always exist", Graph Drawing: 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers, Lecture Notes in Computer Science, vol. 5849, pp. 171–182, doi:10.1007/978-3-642-11805-0_17.
- ↑ Nöllenburg, Martin; Prutkin, Roman (2013), "Euclidean greedy drawings of trees", Proc. 21st European Symposium on Algorithms (ESA 2013), arXiv:1306.5224, Bibcode:2013arXiv1306.5224N.
- ↑ 8.0 8.1 Leighton, Tom; Moitra, Ankur (2010), "Some results on greedy embeddings in metric spaces", Discrete and Computational Geometry, 44 (3): 686–705, doi:10.1007/s00454-009-9227-6, MR 2679063.
- ↑ Angelini, Patrizio; Frati, Fabrizio; Grilli, Luca (2010), "An algorithm to construct greedy drawings of triangulations", Journal of Graph Algorithms and Applications, 14 (1): 19–51, doi:10.7155/jgaa.00197, MR 2595019.
- ↑ Goodrich, Michael T.; Strash, Darren (2009), "Succinct greedy geometric routing in the Euclidean plane", Algorithms and Computation: 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009, Proceedings, Lecture Notes in Computer Science, vol. 5878, Berlin: Springer, pp. 781–791, arXiv:0812.3893, doi:10.1007/978-3-642-10631-6_79, MR 2792775.
- ↑ Schnyder, Walter (1990), "Embedding planar graphs on the grid", Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA), pp. 138–148.
- ↑ Dhandapani, Raghavan (2010), "Greedy drawings of triangulations", Discrete and Computational Geometry, 43 (2): 375–392, doi:10.1007/s00454-009-9235-6, MR 2579703. See also
- ↑ Nöllenburg, Martin; Prutkin, Roman; Rutter, Ignaz (2016), "On self-approaching and increasing-chord drawings of 3-connected planar graphs", Journal of Computational Geometry, 7 (1): 47–69, arXiv:1409.0315, doi:10.20382/jocg.v7i1a3, MR 3463906.
- ↑ Flury, R.; Pemmaraju, S.V.; Wattenhofer, R. (2009), "Greedy routing with bounded stretch", IEEE INFOCOM 2009, pp. 1737–1745, doi:10.1109/INFCOM.2009.5062093.
