ग्रीडी एम्बेडिंग: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
वितरित कंप्यूटिंग और [[ज्यामितीय ग्राफ सिद्धांत]] में, लालची एम्बेडिंग [[दूरसंचार नेटवर्क]] के नोड्स को निर्देशांक निर्दिष्ट करने की प्रक्रिया है | वितरित कंप्यूटिंग और [[ज्यामितीय ग्राफ सिद्धांत]] में, लालची एम्बेडिंग [[दूरसंचार नेटवर्क]] के नोड्स को निर्देशांक निर्दिष्ट करने की प्रक्रिया है जिससे कि नेटवर्क के भीतर संदेशों को रूट करने के लिए [[लालची एल्गोरिदम]] [[भौगोलिक रूटिंग]] का उपयोग करने की अनुमति मिल सके। यद्यपि [[वायरलेस सेंसर नेटवर्क]] में उपयोग के लिए लालची एम्बेडिंग का प्रस्ताव किया गया है, जिसमें नोड्स के पास पहले से ही भौतिक स्थान में स्थिति होती है, ये उपस्तिथा स्थिति लालची एम्बेडिंग द्वारा उन्हें दी गई स्थिति से भिन्न हो सकती हैं, जो कुछ स्थितियों में वर्चुअल स्पेस में बिंदु हो सकती हैं उच्च आयाम का, या [[गैर-यूक्लिडियन ज्यामिति]] में। इस अर्थ में, लालची एम्बेडिंग को [[ग्राफ ड्राइंग]] के रूप के रूप में देखा जा सकता है, जिसमें अमूर्त ग्राफ़ (संचार नेटवर्क) ज्यामितीय स्थान में [[ग्राफ एम्बेडिंग]] होता है। | ||
भौतिक निर्देशांक का उपयोग करने के | भौतिक निर्देशांक का उपयोग करने के अतिरिक्त, आभासी स्थान में निर्देशांक का उपयोग करके भौगोलिक रूटिंग करने का विचार राव एट अल के कारण है।<ref name="rrpss03"/>बाद के विकासों से पता चला है कि प्रत्येक नेटवर्क में [[अतिशयोक्तिपूर्ण विमान]] में संक्षिप्त शीर्ष निर्देशांक के साथ लालची एम्बेडिंग होती है, कि [[ बहुफलकीय ग्राफ |बहुफलकीय ग्राफ]] ़ सहित कुछ ग्राफ़ में [[यूक्लिडियन विमान]] में लालची एम्बेडिंग होती है, और [[यूनिट डिस्क ग्राफ़]] में मध्यम आयामों के यूक्लिडियन स्थानों में लालची एम्बेडिंग होती है कम खिंचाव कारक. | ||
==परिभाषाएँ== | ==परिभाषाएँ== | ||
लालची रूटिंग में, स्रोत नोड एस से गंतव्य नोड टी तक संदेश मध्यवर्ती नोड्स के माध्यम से चरणों के अनुक्रम द्वारा अपने गंतव्य तक जाता है, जिनमें से प्रत्येक संदेश को | लालची रूटिंग में, स्रोत नोड एस से गंतव्य नोड टी तक संदेश मध्यवर्ती नोड्स के माध्यम से चरणों के अनुक्रम द्वारा अपने गंतव्य तक जाता है, जिनमें से प्रत्येक संदेश को निकटतम नोड पर भेजता है जो टी के करीब है। यदि संदेश मध्यवर्ती नोड x तक पहुंचता है जिसका कोई निकटतम t के करीब नहीं है, तो यह प्रगति नहीं कर सकता है और लालची रूटिंग प्रक्रिया विफल हो जाती है। लालची एम्बेडिंग दिए गए ग्राफ़ को इस संपत्ति के साथ एम्बेड करना है कि इस प्रकार की विफलता असंभव है। इस प्रकार, इसे इस गुण के साथ ग्राफ़ के एम्बेडिंग के रूप में वर्णित किया जा सकता है कि प्रत्येक दो नोड्स x और t के लिए, x का निकटतम y उपस्तिथ होता है जैसे कि d(x,t) > d(y,t), जहां d दर्शाता है एम्बेडेड स्थान में दूरी.<ref name="pr05"/> | ||
==बिना लालची एम्बेडिंग वाले ग्राफ़== | ==बिना लालची एम्बेडिंग वाले ग्राफ़== | ||
[[File:Sextic-monomial-dessin.svg|thumb|150px|K<sub>1,6</sub>, यूक्लिडियन विमान में कोई लालची एम्बेडिंग वाला ग्राफ]]प्रत्येक ग्राफ़ में यूक्लिडियन विमान में लालची एम्बेडिंग नहीं होती है; स्टार (ग्राफ सिद्धांत) के द्वारा सरल प्रति उदाहरण दिया गया है<sub>1,6</sub>, आंतरिक नोड और छह पत्तियों वाला पेड़ (ग्राफ सिद्धांत)।<ref name="pr05"/>जब भी इस ग्राफ़ को समतल में एम्बेड किया जाता है, तो इसकी कुछ दो पत्तियों को 60 डिग्री या उससे कम का कोण बनाना चाहिए, जिससे यह पता चलता है कि इन दो पत्तियों में से कम से कम का | [[File:Sextic-monomial-dessin.svg|thumb|150px|K<sub>1,6</sub>, यूक्लिडियन विमान में कोई लालची एम्बेडिंग वाला ग्राफ]]प्रत्येक ग्राफ़ में यूक्लिडियन विमान में लालची एम्बेडिंग नहीं होती है; स्टार (ग्राफ सिद्धांत) के द्वारा सरल प्रति उदाहरण दिया गया है<sub>1,6</sub>, आंतरिक नोड और छह पत्तियों वाला पेड़ (ग्राफ सिद्धांत)।<ref name="pr05"/>जब भी इस ग्राफ़ को समतल में एम्बेड किया जाता है, तो इसकी कुछ दो पत्तियों को 60 डिग्री या उससे कम का कोण बनाना चाहिए, जिससे यह पता चलता है कि इन दो पत्तियों में से कम से कम का निकटतम दूसरे पत्ते के करीब नहीं है। | ||
उच्च आयामों के [[यूक्लिडियन स्थान]]ों में, अधिक ग्राफ़ में लालची एम्बेडिंग हो सकती है; उदाहरण के लिए, के<sub>1,6</sub> त्रि-आयामी यूक्लिडियन अंतरिक्ष में लालची एम्बेडिंग है, जिसमें तारे का आंतरिक नोड मूल पर है और पत्तियां प्रत्येक समन्वय अक्ष के साथ इकाई की दूरी पर हैं। हालाँकि, निश्चित आयाम के प्रत्येक यूक्लिडियन स्थान के लिए, ऐसे ग्राफ़ होते हैं जिन्हें लालच से एम्बेड नहीं किया जा सकता है: जब भी संख्या n अंतरिक्ष की [[चुंबन संख्या समस्या]] से अधिक होती है, तो ग्राफ़ K<sub>1,''n''</sub> कोई लालची एम्बेडिंग नहीं है.<ref name="eg11"/> | उच्च आयामों के [[यूक्लिडियन स्थान]]ों में, अधिक ग्राफ़ में लालची एम्बेडिंग हो सकती है; उदाहरण के लिए, के<sub>1,6</sub> त्रि-आयामी यूक्लिडियन अंतरिक्ष में लालची एम्बेडिंग है, जिसमें तारे का आंतरिक नोड मूल पर है और पत्तियां प्रत्येक समन्वय अक्ष के साथ इकाई की दूरी पर हैं। हालाँकि, निश्चित आयाम के प्रत्येक यूक्लिडियन स्थान के लिए, ऐसे ग्राफ़ होते हैं जिन्हें लालच से एम्बेड नहीं किया जा सकता है: जब भी संख्या n अंतरिक्ष की [[चुंबन संख्या समस्या]] से अधिक होती है, तो ग्राफ़ K<sub>1,''n''</sub> कोई लालची एम्बेडिंग नहीं है.<ref name="eg11"/> | ||
==अतिशयोक्तिपूर्ण और संक्षिप्त एम्बेडिंग== | ==अतिशयोक्तिपूर्ण और संक्षिप्त एम्बेडिंग== | ||
यूक्लिडियन विमान के | यूक्लिडियन विमान के स्थिति के विपरीत, प्रत्येक नेटवर्क में हाइपरबोलिक विमान में लालची एम्बेडिंग होती है। [[रॉबर्ट क्लेनबर्ग]] द्वारा इस परिणाम के मूल प्रमाण में, नोड स्थितियों को उच्च परिशुद्धता के साथ निर्दिष्ट करने की आवश्यकता थी,<ref name="k07"/>लेकिन बाद में यह दिखाया गया कि, नेटवर्क के फैले हुए पेड़ के [[भारी पथ अपघटन]] का उपयोग करके, प्रति बिंदु बिट्स की केवल लॉगरिदमिक संख्या का उपयोग करके, प्रत्येक नोड को संक्षेप में प्रस्तुत करना संभव है।<ref name="eg11"/>इसके विपरीत, ऐसे ग्राफ़ उपस्तिथ हैं जिनमें यूक्लिडियन विमान में लालची एम्बेडिंग है, लेकिन जिसके लिए ऐसे किसी भी एम्बेडिंग के लिए प्रत्येक बिंदु के कार्टेशियन निर्देशांक के लिए बिट्स की बहुपद संख्या की आवश्यकता होती है।<ref name="css09"/><ref name="adf10"/> | ||
==ग्राफ़ के विशेष वर्ग== | ==ग्राफ़ के विशेष वर्ग== | ||
===पेड़=== | ===पेड़=== | ||
ट्री का वर्ग (ग्राफ सिद्धांत) जो यूक्लिडियन विमान में लालची एम्बेडिंग को स्वीकार करता है, उसे पूरी तरह से चित्रित किया गया है, और पेड़ का लालची एम्बेडिंग [[रैखिक समय]] में पाया जा सकता है जब वह | ट्री का वर्ग (ग्राफ सिद्धांत) जो यूक्लिडियन विमान में लालची एम्बेडिंग को स्वीकार करता है, उसे पूरी तरह से चित्रित किया गया है, और पेड़ का लालची एम्बेडिंग [[रैखिक समय]] में पाया जा सकता है जब वह उपस्तिथ होता है।<ref name="np13"/> | ||
अधिक सामान्य ग्राफ़ के लिए, कुछ लालची एम्बेडिंग एल्गोरिदम जैसे कि क्लेनबर्ग द्वारा बनाया गया<ref name="k07"/>दिए गए ग्राफ़ का स्पैनिंग ट्री ढूंढकर प्रारंभ करें, और फिर स्पैनिंग ट्री का लालची एम्बेडिंग बनाएं। परिणाम आवश्यक रूप से पूरे ग्राफ का लालची एम्बेडिंग भी है। हालाँकि, ऐसे ग्राफ़ | अधिक सामान्य ग्राफ़ के लिए, कुछ लालची एम्बेडिंग एल्गोरिदम जैसे कि क्लेनबर्ग द्वारा बनाया गया<ref name="k07"/>दिए गए ग्राफ़ का स्पैनिंग ट्री ढूंढकर प्रारंभ करें, और फिर स्पैनिंग ट्री का लालची एम्बेडिंग बनाएं। परिणाम आवश्यक रूप से पूरे ग्राफ का लालची एम्बेडिंग भी है। हालाँकि, ऐसे ग्राफ़ उपस्तिथ हैं जिनमें यूक्लिडियन विमान में लालची एम्बेडिंग है, लेकिन जिनके लिए किसी भी फैले हुए पेड़ में लालची एम्बेडिंग नहीं है।<ref name="lm10"/> | ||
===तलीय रेखांकन=== | ===तलीय रेखांकन=== | ||
{{unsolved|mathematics|Does every [[polyhedral graph]] have a planar greedy embedding with convex faces?}} | {{unsolved|mathematics|Does every [[polyhedral graph]] have a planar greedy embedding with convex faces?}} | ||
{{harvtxt|Papadimitriou|Ratajczak|2005}} [[अनुमान]] लगाया गया है कि प्रत्येक पॉलीहेड्रल ग्राफ ([[ के-वर्टेक्स-कनेक्टेड ग्राफ़ | के-वर्टेक्स-कनेक्टेड ग्राफ़]] | 3-वर्टेक्स-कनेक्टेड [[ समतलीय ग्राफ |समतलीय ग्राफ]] , या स्टीनिट्ज़ के प्रमेय द्वारा समतुल्य उत्तल पॉलीहेड्रॉन का ग्राफ) में यूक्लिडियन विमान में लालची एम्बेडिंग होती है।<ref name="pr05"/>[[कैक्टस ग्राफ]]़ के गुणों का दोहन करके, {{harvtxt|Leighton|Moitra|2010}} अनुमान सिद्ध हुआ;<ref name="lm10"/><ref name="afg10"/>इन ग्राफ़ों की लालची एम्बेडिंग को लघुगणकीय रूप से प्रति समन्वय कई बिट्स के साथ संक्षेप में परिभाषित किया जा सकता है।<ref name="gs09"/> हालाँकि, इस प्रमाण के अनुसार निर्मित लालची एम्बेडिंग आवश्यक रूप से समतल एम्बेडिंग नहीं हैं, क्योंकि उनमें किनारों के जोड़े के बीच क्रॉसिंग | {{harvtxt|Papadimitriou|Ratajczak|2005}} [[अनुमान]] लगाया गया है कि प्रत्येक पॉलीहेड्रल ग्राफ ([[ के-वर्टेक्स-कनेक्टेड ग्राफ़ | के-वर्टेक्स-कनेक्टेड ग्राफ़]] | 3-वर्टेक्स-कनेक्टेड [[ समतलीय ग्राफ |समतलीय ग्राफ]] , या स्टीनिट्ज़ के प्रमेय द्वारा समतुल्य उत्तल पॉलीहेड्रॉन का ग्राफ) में यूक्लिडियन विमान में लालची एम्बेडिंग होती है।<ref name="pr05"/>[[कैक्टस ग्राफ]]़ के गुणों का दोहन करके, {{harvtxt|Leighton|Moitra|2010}} अनुमान सिद्ध हुआ;<ref name="lm10"/><ref name="afg10"/>इन ग्राफ़ों की लालची एम्बेडिंग को लघुगणकीय रूप से प्रति समन्वय कई बिट्स के साथ संक्षेप में परिभाषित किया जा सकता है।<ref name="gs09"/> हालाँकि, इस प्रमाण के अनुसार निर्मित लालची एम्बेडिंग आवश्यक रूप से समतल एम्बेडिंग नहीं हैं, क्योंकि उनमें किनारों के जोड़े के बीच क्रॉसिंग सम्मिलित हो सकती है। अधिकतम तलीय रेखांकन के लिए, जिसमें प्रत्येक फलक त्रिभुज है, लालची तलीय एम्बेडिंग को फैरी के प्रमेय के भारित संस्करण में नैस्टर-कुराटोव्स्की-मज़ुरकिविज़ लेम्मा को लागू करके पाया जा सकता है। श्नाइडर के स्ट्रेट-लाइन एम्बेडिंग एल्गोरिदम।<ref name="s90"/><ref name="d10"/>मजबूत पापादिमित्रीउ-रतज्ज़क अनुमान, कि प्रत्येक बहुफलकीय ग्राफ में तलीय लालची एम्बेडिंग होती है जिसमें सभी चेहरे उत्तल होते हैं, अप्रमाणित रहता है।<ref>{{citation | ||
| last1 = Nöllenburg | first1 = Martin | | last1 = Nöllenburg | first1 = Martin | ||
| last2 = Prutkin | first2 = Roman | | last2 = Prutkin | first2 = Roman | ||
| Line 32: | Line 32: | ||
| year = 2016| arxiv = 1409.0315}}.</ref> | | year = 2016| arxiv = 1409.0315}}.</ref> | ||
===[[यूनिट डिस्क]] ग्राफ़=== | ===[[यूनिट डिस्क]] ग्राफ़=== | ||
वायरलेस सेंसर नेटवर्क जो लालची एम्बेडिंग एल्गोरिदम का लक्ष्य हैं, उन्हें | वायरलेस सेंसर नेटवर्क जो लालची एम्बेडिंग एल्गोरिदम का लक्ष्य हैं, उन्हें अधिकांशतः यूनिट डिस्क ग्राफ़ के रूप में मॉडल किया जाता है, ग्राफ़ जिसमें प्रत्येक नोड को यूनिट डिस्क के रूप में दर्शाया जाता है और प्रत्येक किनारा गैर-रिक्त चौराहे के साथ डिस्क की जोड़ी से मेल खाता है। ग्राफ़ के इस विशेष वर्ग के लिए, पॉलीलॉगरिदमिक आयाम के यूक्लिडियन स्पेस में संक्षिप्त लालची एम्बेडिंग को ढूंढना संभव है, अतिरिक्त संपत्ति के साथ ग्राफ़ में दूरियों को एम्बेडिंग में दूरियों द्वारा सटीक रूप से अनुमानित किया जाता है, जिससे कि लालची रूटिंग द्वारा अपनाए गए पथ हों छोटा।<ref name="fpw09"/> | ||
==संदर्भ== | ==संदर्भ== | ||
{{reflist|30em|refs= | {{reflist|30em|refs= | ||
Revision as of 20:33, 6 July 2023
वितरित कंप्यूटिंग और ज्यामितीय ग्राफ सिद्धांत में, लालची एम्बेडिंग दूरसंचार नेटवर्क के नोड्स को निर्देशांक निर्दिष्ट करने की प्रक्रिया है जिससे कि नेटवर्क के भीतर संदेशों को रूट करने के लिए लालची एल्गोरिदम भौगोलिक रूटिंग का उपयोग करने की अनुमति मिल सके। यद्यपि वायरलेस सेंसर नेटवर्क में उपयोग के लिए लालची एम्बेडिंग का प्रस्ताव किया गया है, जिसमें नोड्स के पास पहले से ही भौतिक स्थान में स्थिति होती है, ये उपस्तिथा स्थिति लालची एम्बेडिंग द्वारा उन्हें दी गई स्थिति से भिन्न हो सकती हैं, जो कुछ स्थितियों में वर्चुअल स्पेस में बिंदु हो सकती हैं उच्च आयाम का, या गैर-यूक्लिडियन ज्यामिति में। इस अर्थ में, लालची एम्बेडिंग को ग्राफ ड्राइंग के रूप के रूप में देखा जा सकता है, जिसमें अमूर्त ग्राफ़ (संचार नेटवर्क) ज्यामितीय स्थान में ग्राफ एम्बेडिंग होता है।
भौतिक निर्देशांक का उपयोग करने के अतिरिक्त, आभासी स्थान में निर्देशांक का उपयोग करके भौगोलिक रूटिंग करने का विचार राव एट अल के कारण है।[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.
