अंतर्निहित ग्राफ

From Vigyanwiki

ग्राफ़ एल्गोरिदम के अध्ययन में, एक अंतर्निहित ग्राफ़ प्रतिनिधित्व (या अधिक सरल रूप से अंतर्निहित ग्राफ़) एक ऐसा ग्राफ़ होता है जिसके शीर्ष या किनारों को कंप्यूटर की मेमोरी में स्पष्ट ऑब्जेक्ट्स, बल्कि किसी अन्य इनपुट से एल्गोरिदमिक रूप से निर्धारित होते हैं, उदाहरण के लिए एक गणना योग्य फ़ंक्शन के रूप में दर्शाया नहीं जाता है।

परिवेश का प्रतिनिधित्व

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

कम्प्यूटेशनल सम्मिश्रता सिद्धांत में, अंतर्निहित ग्राफ़ के संबंध में कई सम्मिश्रता वर्गों को परिभाषित किया गया है, जैसा कि एक शीर्ष के परिवेश को सूचीबद्ध करने के लिए एक नियम या एल्गोरिदम द्वारा ऊपर परिभाषित किया गया है। उदाहरण के लिए, पीपीए समस्याओं का वह वर्ग है जिसमें इनपुट के रूप में एक अप्रत्यक्ष अंतर्निहित ग्राफ दिया जाता है (जिसमें कोने n-बिट बाइनरी स्ट्रिंग होते हैं, किसी भी शीर्ष के परिवेश को सूचीबद्ध करने के लिए एक बहुपद समय एल्गोरिदम के साथ) और विषम डिग्री का एक शीर्ष होता है ग्राफ़ में, और विषम डिग्री का दूसरा शीर्ष खोजना होगा। हाथ मिलाने की प्रमेयिका द्वारा, ऐसा शीर्ष उपस्थित है; NP में किसी को ढूंढना एक समस्या है, लेकिन जिन समस्याओं को इस तरह से परिभाषित किया जा सकता है, जरूरी नहीं कि वे NP-पूर्ण हों, क्योंकि यह अज्ञात है कि PPA = NP है या नहीं। PPAD अंतर्निहित निर्देशित ग्राफ़ पर परिभाषित एक अनुरूप वर्ग है जिसने एल्गोरिथम गेम सिद्धांत में ध्यान आकर्षित किया है क्योंकि इसमें नैश संतुलन की गणना करने की समस्या सम्मिलित है।[3] एक अंतर्निहित ग्राफ़ में एक शीर्ष से दूसरे शीर्ष तक पहुंच योग्यता का परीक्षण करने की समस्या का उपयोग NL सहित अंतरिक्ष-बद्ध गैर-नियतात्मक सम्मिश्रता वर्गों को चिह्नित करने के लिए भी किया जा सकता है (समस्याओं का वर्ग जिसे अंतर्निहित निर्देशित ग्राफ़ में पहुंच योग्यता द्वारा विशेषता दी जा सकती है जिनके शीर्ष O(log n)-bit बिटस्ट्रिंग्स), SL (अप्रत्यक्ष ग्राफ़ के लिए अनुरूप वर्ग), और पीएसपीएसीई (समस्याओं का वर्ग जिसे बहुपद-लंबाई बिटस्ट्रिंग्स के साथ अंतर्निहित ग्राफ़ में पहुंच द्वारा विशेषता दी जा सकती है)। इस सम्मिश्रता-सैद्धांतिक संदर्भ में, एक अंतर्निहित ग्राफ़ के शीर्ष एक गैर-नियतात्मक ट्यूरिंग मशीन की स्थितियों का प्रतिनिधित्व कर सकते हैं, और किनारे संभावित राज्य परिवर्तनों का प्रतिनिधित्व कर सकते हैं, लेकिन अंतर्निहित ग्राफ़ का उपयोग कई अन्य प्रकार की संयोजन संरचना का प्रतिनिधित्व करने के लिए भी किया जा सकता है।[4] PLS, एक अन्य सम्मिश्रता वर्ग, एक अंतर्निहित ग्राफ़ में स्थानीय ऑप्टिमा खोजने की सम्मिश्रता को पकड़ता है।[5]

सम्मिश्रता वर्गों के बीच अलगाव को सिद्ध करने के लिए निहित ग्राफ मॉडल का उपयोग सापेक्षता के एक रूप के रूप में भी किया गया है जो गैर-सापेक्ष मॉडल के लिए ज्ञात पृथक्करण से अधिक प्रबल हैं। उदाहरण के लिए, चाइल्ड्स एट अल. ग्राफ़ ट्रैवर्सल समस्या को परिभाषित करने के लिए अंतर्निहित ग्राफ़ के परिवेश निरूपण का उपयोग किया जाता है जिसे क्वांटम कंप्यूटर पर बहुपद समय में हल किया जा सकता है लेकिन किसी भी शास्त्रीय कंप्यूटर पर हल करने के लिए घातीय समय की आवश्यकता होती है।[6]

अडजासेन्सी (आसन्न ) लेबलिंग स्कीम्स

ग्राफ़ के कुशल प्रतिनिधित्व के संदर्भ में, जे.एच. मुलर ने ग्राफ़ के किसी दिए गए समूह F में ग्राफ़ G के लिए एक स्थानीय संरचना या आसन्न लेबलिंग स्कीम को परिभाषित किया, जो कि G के प्रत्येक शीर्ष पर O(log n)-बिट अभिनिर्धारित्र का असाइनमेंट है, एक एल्गोरिथ्म के साथ (जो F पर निर्भर हो सकता है लेकिन व्यक्तिगत ग्राफ G से स्वतंत्र है) जो इनपुट के रूप में दो शीर्ष पहचानकर्ताओं को लेता है और निर्धारित करता है कि वे G में एक किनारे के अंतिम बिंदु हैं या नहीं। यानी, इस प्रकार का अंतर्निहित प्रतिनिधित्व है आसन्न मैट्रिक्स के अनुरूप: यह जांचना सीधा है कि क्या दो शीर्ष आसन्न हैं, लेकिन किसी शीर्ष के परिवेश को खोजने में सभी शीर्षों के माध्यम से लूपिंग और परीक्षण करना सम्मिलित हो सकता है कि कौन परिवेश हैं।[7]

निकटवर्ती लेबलिंग योजनाओं वाले ग्राफ़ समूहों में सम्मिलित हैं:

परिबद्ध डिग्री ग्राफ़
यदि G के प्रत्येक शीर्ष पर अधिकतम d निकट हैं, तो कोई व्यक्ति G के शीर्षों को 1 से n तक क्रमांकित कर सकता है और किसी शीर्ष के लिए अभिनिर्धारित्र को उसकी अपनी संख्या और उसके परिवेश की संख्या का (d + 1)-टुपल मान सकता है। दो शीर्ष आसन्न होते हैं जब उनके पहचानकर्ताओं में पहले नंबर बाद में दूसरे शीर्ष के अभिनिर्धारित्र में दिखाई देते हैं। अधिक सामान्यतः समान दृष्टिकोण का उपयोग सीमाबद्ध आर्बोरिसिटी या सीमाबद्ध अध:पतन वाले ग्राफ़ के लिए एक अंतर्निहित प्रतिनिधित्व प्रदान करने के लिए किया जा सकता है, जिसमें समतल ग्राफ़ और किसी भी अल्प-संवृत ग्राफ समूह में ग्राफ़ सम्मिलित हैं।[8][9]:
इंटरसेक्शन ग्राफ
एक अंतराल ग्राफ वास्तविक रेखा में रेखा खंडों के एक समूह का प्रतिच्छेदन ग्राफ है। इसे एक आसन्न लेबलिंग स्कीम दी जा सकती है जिसमें रेखा खंडों के अंतिम बिंदुओं को 1 से 2n तक क्रमांकित किया जाता है और ग्राफ़ के प्रत्येक शीर्ष को उसके संबंधित अंतराल के दो समापन बिंदुओं की संख्या द्वारा दर्शाया जाता है। इस प्रतिनिधित्व के साथ, कोई यह जांच सकता है कि क्या दो शीर्ष उन संख्याओं की तुलना करके आसन्न हैं जो उनका प्रतिनिधित्व करते हैं और यह सत्यापित करते हैं कि ये संख्याएं ओवरलैपिंग अंतराल को परिभाषित करती हैं। यही दृष्टिकोण अन्य ज्यामितीय प्रतिच्छेदन ग्राफ के लिए भी काम करता है, जिसमें सीमाबद्ध बॉक्सिसिटी और वृत्त ग्राफ और इन समूहों के उपकुल जैसे दूरी-वंशानुगत ग्राफ़ और कोग्राफ़ सम्मिलित हैं।[8][10] हालाँकि, एक ज्यामितीय प्रतिच्छेदन ग्राफ प्रतिनिधित्व हमेशा एक आसन्नता लेबलिंग स्कीम के अस्तित्व का संकेत नहीं देता है, क्योंकि प्रत्येक ज्यामितीय वस्तु को निर्दिष्ट करने के लिए बिट्स की लघुगणकीय संख्या से अधिक की आवश्यकता हो सकती है। उदाहरण के लिए, एक ग्राफ़ को एक इकाई डिस्क ग्राफ़ के रूप में प्रस्तुत करने के लिए डिस्क केंद्रों के निर्देशांक के लिए तेजी से कई बिट्स की आवश्यकता हो सकती है।[11]:
निम्न-आयामी तुलनीयता ग्राफ़
आंशिक रूप से ऑर्डर किए गए समूह के लिए तुलनीयता ग्राफ़ में प्रत्येक समूह तत्व के लिए एक शीर्ष और आंशिक क्रम से संबंधित दो समूह तत्वों के बीच एक किनारा होता है। आंशिक ऑर्डर का ऑर्डर आयाम रैखिक ऑर्डरों की न्यूनतम संख्या है जिसका प्रतिच्छेदन दिया गया आंशिक ऑर्डर है। यदि किसी आंशिक क्रम में सीमित क्रम आयाम है, तो इसके तुलनीयता ग्राफ में शीर्षों के लिए एक आसन्नता लेबलिंग स्कीम को प्रत्येक परिभाषित रैखिक क्रम में अपनी स्थिति के साथ प्रत्येक शीर्ष को लेबल करके परिभाषित किया जा सकता है, और यह निर्धारित किया जा सकता है कि यदि प्रत्येक संगत जोड़ी है तो दो शीर्ष आसन्न हैं उनके लेबल में संख्याओं का एक-दूसरे जोड़े के समान क्रम संबंध है। विशेष रूप से, यह कॉर्डल तुलनीयता ग्राफ़ के लिए एक आसन्नता लेबलिंग स्कीम की अनुमति देता है, जो अधिकतम चार आयामों के आंशिक आदेशों से आते हैं।[12][13]

अंतर्निहित ग्राफ़ अनुमान

Unsolved problem in mathematics:

Does every slowly-growing hereditary family of graphs have an implicit representation?

(more unsolved problems in mathematics)

सभी ग्राफ़ समूहों में स्थानीय संरचनाएँ नहीं होती हैं। कुछ समूहों के लिए, एक साधारण गिनती तर्क साबित करता है कि आसन्नता लेबलिंग योजनाएं उपस्थित नहीं हैं: पूरे ग्राफ का प्रतिनिधित्व करने के लिए केवल O(n log n) बिट्स का उपयोग किया जा सकता है, इसलिए इस प्रकार का प्रतिनिधित्व केवल तभी उपस्थित हो सकता है जब एन-वर्टेक्स की संख्या दिए गए समूह F में ग्राफ़ अधिकतम 2O(n log n) है। ग्राफ़ समूह जिनके पास इससे बड़ी संख्या में ग्राफ़ हैं, जैसे द्विदलीय ग्राफ़ या त्रिकोण-मुक्त ग्राफ़, उनके पास आसन्नता लेबलिंग स्कीम नहीं हैं।[8][10] हालाँकि, ग्राफ़ के ऐसे समूहों में भी, जिनमें समूह में ग्राफ़ की संख्या कम है, आसन्न लेबलिंग स्कीम नहीं हो सकती है; उदाहरण के लिए, शीर्षों से कम किनारों वाले ग्राफ़ के समूह में 2O(n log n) n-वर्टेक्स ग्राफ़ हैं, लेकिन कोई आसन्नता लेबलिंग स्कीम नहीं है, क्योंकि इस समूह में कोई भी नया जोड़कर किसी भी दिए गए ग्राफ़ को बड़े ग्राफ़ में बदल सकता है प्रत्येक किनारे के लिए पृथक शीर्ष, उसकी लेबलेबिलिटी को बदले बिना।[7][10] कन्नन एट अल. पूछा गया कि क्या निषिद्ध सबग्राफ लक्षण वर्णन और अधिकतम 2O(n log n) n-वर्टेक्स ग्राफ एक साथ मिलकर आसन्न लेबलिंग स्कीम के अस्तित्व की गारंटी देने के लिए पर्याप्त हैं; यह प्रश्न, जिसे स्पिनराड ने अनुमान के रूप में दोहराया है, खुला रहता है।[8][10] ग्राफ़ के समूहों में से जो अनुमान की शर्तों को पूरा करते हैं और जिनके लिए कोई ज्ञात आसन्नता लेबलिंग स्कीम नहीं है, वे डिस्क ग्राफ़ और लाइन सेगमेंट प्रतिच्छेदन ग्राफ़ के समूह हैं।

लेबलिंग स्कीम्स और प्रेरित सार्वभौमिक ग्राफ

यदि एक ग्राफ समूह F में एक आसन्नता लेबलिंग स्कीम है, फिर n-वर्टेक्स ग्राफ़ में F को बहुपद आकार के एक सामान्य प्रेरित सार्वभौमिक ग्राफ के प्रेरित उपग्राफ के रूप में दर्शाया जा सकता है, ग्राफ में सभी संभावित शीर्ष अभिनिर्धारित्र सम्मिलित हैं। इसके विपरीत, यदि इस प्रकार का एक प्रेरित सार्वभौमिक ग्राफ बनाया जा सकता है, तो इसके शीर्षों की पहचान को आसन्न लेबलिंग स्कीम में लेबल के रूप में उपयोग किया जा सकता है।[8] अंतर्निहित ग्राफ प्रतिनिधित्व के इस अनुप्रयोग के लिए, यह महत्वपूर्ण है कि लेबल जितना संभव हो उतना कम बिट्स का उपयोग करें, क्योंकि लेबल में बिट्स की संख्या सीधे प्रेरित सार्वभौमिक ग्राफ में शीर्षों की संख्या में परिवर्तित हो जाती है। अलस्ट्रुप और रौहे ने दिखाया कि किसी भी ट्री में प्रति लेबल log2 n + O(log* n) बिट्स के साथ एक आसन्न लेबलिंग स्कीम होती है, जिससे यह पता चलता है कि आर्बोरिसिटी के वाले किसी भी ग्राफ में k log2 n + O(log* n) के साथ एक स्कीम होती है। प्रति लेबल बिट्स और nk2O(log* n) शीर्षों के साथ एक सार्वभौमिक ग्राफ़ होते हैं। विशेष रूप से, समतलीय ग्राफ़ में अधिकतम तीन आर्बोरिसिटी होती है, इसलिए उनके पास लगभग-घन शीर्षों की संख्या के साथ सार्वभौमिक ग्राफ़ होते हैं।[14] इस बाउंड को गैवोइल और लैबोरेल द्वारा सुधारा गया था, जिन्होंने दिखाया था कि प्लेनर ग्राफ़ और माइनर-क्लोज्ड ग्राफ़ समूहों में प्रति लेबल 2 log2 n + O(log log n)बिट्स के साथ एक लेबलिंग स्कीम होती है, और बाउंड ट्रीविड्थ के ग्राफ़ में log2 के साथ एक लेबलिंग स्कीम होती है। log2 n + O(log log n) बिट्स प्रति लेबल।[15] बोनामी, गैवोइल और पिलिकज़ुक द्वारा समतलीय ग्राफ़ की सीमा में फिर से सुधार किया गया, जिन्होंने दिखाया कि समतलीय ग्राफ़ में प्रति लेबल (4/3+o(1))log2 n बिट्स के साथ एक लेबलिंग स्कीम होती है।[16] अंत में डुज्मोविक और अन्य ने दिखाया कि समतलीय ग्राफ़ में (1+o(1))log2 n बिट्स प्रति लेबल के साथ एक लेबलिंग स्कीम होती है जो n1+o(1) शीर्षों के साथ एक सार्वभौमिक ग्राफ़ देती है।[17]

अस्थिरता

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

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

बेंडर और रॉन ने दिखाया है कि, अपवंचनता अनुमान के लिए उपयोग किए गए एक ही मॉडल में, केवल निरंतर समय में निर्देशित एसाइक्लिक ग्राफ़ को उन ग्राफ़ से अलग करना संभव है जो एसाइक्लिक होने से बहुत दूर हैं। इसके विपरीत, प्रतिवैस-आधारित अंतर्निहित ग्राफ़ मॉडल, [20] ट्री में इतना शीघ्र समय संभव नहीं है

यह भी देखें

संदर्भ

  1. ↑ Korf, Richard E. (2008), "Linear-time disk-based implicit graph search", Journal of the ACM, 55 (6), Article 26, 40pp, doi:10.1145/1455248.1455250, MR 2477486.
  2. ↑ Korf, Richard E. (2008), "Minimizing disk I/O in two-bit breadth-first search" (PDF), Proc. 23rd AAAI Conf. on Artificial Intelligence, pp. 317–324, The standard 3×3×3 Rubik's Cube contains 4.3252 × 1019 states, and is too large to search exhaustively.
  3. ↑ Papadimitriou, Christos (1994), "On the complexity of the parity argument and other inefficient proofs of existence" (PDF), Journal of Computer and System Sciences, 48 (3): 498–532, doi:10.1016/S0022-0000(05)80063-7, archived from the original (PDF) on 2016-03-04, retrieved 2011-07-12
  4. ↑ Immerman, Neil (1999), "Exercise 3.7 (Everything is a Graph)", Descriptive Complexity, Graduate Texts in Computer Science, Springer-Verlag, p. 48, ISBN 978-0-387-98600-5.
  5. ↑ Yannakakis, Mihalis (2009), "Equilibria, fixed points, and complexity classes", Computer Science Review, 3 (2): 71–85, arXiv:0802.2831, doi:10.1016/j.cosrev.2009.03.004.
  6. ↑ Childs, Andrew M.; Cleve, Richard; Deotto, Enrico; Farhi, Edward; Gutmann, Sam; Spielman, Daniel A. (2003), "Exponential algorithmic speedup by a quantum walk", Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, New York: ACM, pp. 59–68, arXiv:quant-ph/0209131, doi:10.1145/780542.780552, MR 2121062.
  7. ↑ 7.0 7.1 Muller, John Harold (1988), Local structure in graph classes, Ph.D. thesis, Georgia Institute of Technology.
  8. ↑ 8.0 8.1 8.2 8.3 8.4 Kannan, Sampath; Naor, Moni; Rudich, Steven (1992), "Implicit representation of graphs", SIAM Journal on Discrete Mathematics, 5 (4): 596–603, doi:10.1137/0405049, MR 1186827.
  9. ↑ Chrobak, Marek; Eppstein, David (1991), "Planar orientations with low out-degree and compaction of adjacency matrices" (PDF), Theoretical Computer Science, 86 (2): 243–266, doi:10.1016/0304-3975(91)90020-3.
  10. ↑ 10.0 10.1 10.2 10.3 Spinrad, Jeremy P. (2003), "2. Implicit graph representation", Efficient Graph Representations, pp. 17–30, ISBN 0-8218-2815-0.
  11. ↑ Kang, Ross J.; Müller, Tobias (2011), Sphere and dot product representations of graphs (PDF), archived from the original (PDF) on 2012-03-16, retrieved 2011-07-12.
  12. ↑ Ma, Tze Heng; Spinrad, Jeremy P. (1991), "Cycle-free partial orders and chordal comparability graphs", Order, 8 (1): 49–61, doi:10.1007/BF00385814, MR 1129614.
  13. ↑ Curtis, Andrew R.; Izurieta, Clemente; Joeris, Benson; Lundberg, Scott; McConnell, Ross M. (2010), "An implicit representation of chordal comparability graphs in linear time", Discrete Applied Mathematics, 158 (8): 869–875, doi:10.1016/j.dam.2010.01.005, MR 2602811.
  14. ↑ Alstrup, Stephen; Rauhe, Theis (2002), "Small induced-universal graphs and compact implicit graph representations" (PDF), Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pp. 53–62, doi:10.1109/SFCS.2002.1181882, archived from the original (PDF) on 2011-09-27, retrieved 2011-07-13.
  15. ↑ Arnaud, Labourel; Gavoille, Cyril (2007), "Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs" (PDF), Proceedings of the 15th annual European Symposium on Algorithms, pp. 582–593, doi:10.1007/978-3-540-75520-3_52.
  16. ↑ Bonamy, Marthe; Gavoille, Cyril; Pilipczuk, Michał (2020), "Shorter Labeling Schemes for Planar Graphs", Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, pp. 446–462, arXiv:1908.03341, doi:10.1007/978-3-540-75520-3_52.
  17. ↑ Dujmović, Vida; Esperet, Louis; Joret, Gwenaël; Gavoille, Cyril; Micek, Piotr; Morin, Pat (2020), "Adjacency Labelling for Planar Graphs (and Beyond)", 61st IEEE Annual Symposium on Foundations of Computer Science]], pp. 577–588, arXiv:2003.04280, doi:10.1007/978-3-540-75520-3_52.
  18. ↑ Rivest, Ronald L.; Vuillemin, Jean (1975), "A generalization and proof of the Aanderaa-Rosenberg conjecture", Proc. 7th ACM Symposium on Theory of Computing, Albuquerque, New Mexico, United States, pp. 6–11, doi:10.1145/800116.803747{{citation}}: CS1 maint: location missing publisher (link).
  19. ↑ Kahn, Jeff; Saks, Michael; Sturtevant, Dean (1983), "A topological approach to evasiveness", Symposium on Foundations of Computer Science, Los Alamitos, CA, USA: IEEE Computer Society, pp. 31–33, doi:10.1109/SFCS.1983.4.
  20. ↑ Bender, Michael A.; Ron, Dana (2000), "Testing acyclicity of directed graphs in sublinear time", Automata, languages and programming (Geneva, 2000), Lecture Notes in Comput. Sci., vol. 1853, Berlin: Springer, pp. 809–820, doi:10.1007/3-540-45022-X_68, MR 1795937.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=अंतर्निहित_ग्राफ&oldid=264580’